\documentclass[a4paper,10pt,twoside]{article}

%%%%%%%%%%%%%%%%%%%% IDEA %%%%%%%%%%%%%%%%%%%%
%%%%%
%%%* Estudiar IA en juegos
%%%* Falencias de la industria
%%%* Interaccion con potenciales
%%%* Interaccion con Reglas
%%%* Sensores (Vision - Presion)
%%%* CA
%%%* CA + Reglas + Sensores
%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\newenvironment{mylisting}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\scriptsize\bfseries}
{\end{list}}

\newenvironment{mytinylisting}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\tiny\bfseries}
{\end{list}}

\usepackage{amsmath}

% Paquete para urls
\usepackage{url}
%\usepackage{cite}

% Links en indice
%\usepackage{hyperref}
%\hypersetup{linktocpage}

% Paquetes para el idioma, las tildes, etc.
\usepackage[activeacute,spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fontenc}
\usepackage{textcomp}

%\usepackage{graphicx}
%\usepackage[pdftex]{graphicx}
\usepackage[dvips]{graphicx}
%\DeclareGraphicsExtensions{.bmp, .png, .pdf, .jpg, .jpeg, .eps}
\usepackage{subfig}

\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhf{}
%\fancyfoot{}

\fancyhead[RE]{Comportamiento Grupal e Información Sensorial}
\fancyhead[LO]{\rightmark}
\fancyhead[RO,LE]{\thepage}
%\fancyhead[RE]{Comportamiento Grupal e Información Sensorial}
\fancyfoot[CO,CE]{Castro, Ramiro David}
%\fancyfoot[RO, LE] {\thepage}

\renewcommand{\topfraction}{0.85}
\renewcommand{\textfraction}{0.1}
\renewcommand{\floatpagefraction}{0.75}

%\usepackage[numbers,sort&compress]{natbib}
%\bibliographystyle{unsrtnat}
\bibliographystyle{unsrt}
%\bibliography{/home/ramiro/Facu/Swarm.Intelligence/ProyectoTesis/swarm/thesis-swarm/biblio.bib}

%opening
\title{\begin{center}
{\large \textsc{Facultad de Matemática, Astronomía y Física}}\\[0.2cm]
{\textsc{Universidad Nacional de Córdoba}}\\[0.4cm]
\includegraphics[width=0.18\textwidth]{img/escudo-unc} \\ [1cm]
\begin{flushright} \Large
{
\textbf{Comportamiento Grupal e Información Sensorial}
}
\end{flushright}
\end{center}}


\author{\vspace{6.0cm}\\
\textbf{Directores }\\
		MSc. Carbajal Juan Pablo - \texttt{carbajal@ifi.uzh.ch}\\
		Dr. Blanco Javier - \texttt{blanco@mate.uncor.edu.ar}\\
\\\textbf{Alumno} \\
		Castro, Ramiro David - \texttt{castro.ramiro@gmail.com}}

\begin{document}

\maketitle

\clearpage
\thispagestyle{empty}
\mbox{}
\clearpage

\newpage

\tableofcontents

\clearpage
\thispagestyle{empty}
\mbox{}
\clearpage

\newpage
\begin{abstract}
En esta tesis se estudiaron técnicas relacionadas a \textit{Swarm Intelligence} y su aplicación en videojuegos. También se implementaron \textit{Autómatas Celulares} para la modelación de \textit{entornos dinámicos}. Actualmente para la industria de los videojuegos son ramas muy activas las que estudian los problemas de \textit{Movimiento de los Agentes (Character Motion)} y la simulación de entornos dinámicos. Lo que se propone es estudiar técnicas basadas en \textit{AI} y combinarlas con el uso de \textit{CA} para brindar una solución posible a este problema. Se comparan distintas técnicas de swarm intelligence y se analizan pros y contras de la solución ofrecida. También se remarcan posibles aplicaciones y trabajo futuro.

\end{abstract}
\newpage
\section*{Agradecimientos}

Primero que nada a mis padres, si no fuera por su apoyo desde pequeño no estaría acá. Gracias por todo lo que me dieron. Gracias por entenderme siempre, por compartir su experiencia de vida, gracias por sus consejos y por a la vez dejarme elegir y equivocarme si era necesario. Los voy a admirar toda mi vida por sus logros. Nada hubiera sido posible si ellos no hubiesen enriquecido mi crecimiento y no hubiesen confiado en mi. A mis hermanos, Sofía y Gonzalo, que pasé casi toda mi vida compartiendo espacios con ellos y supieron ayudarme y entenderme siempre.

A mis amigos de la facultad. Luis Barrueco, que me acompaño en momentos de estudio y grupos. Luis Ferrer, que siempre estuvo dispuesto a prestar tiempo de su vida en explicar cuestiones formales y demostraciones que se escapaban. A Mati Bellone, ahora felizmente casado, con quien pasamos muchas de las primeras horas de la carrera juntos y supo mostrarme lo que es la eficiencia del trabajo. A Pablo Dal Lago y Lucas Rearte que siempre fueron fuente de inspiración, aportando buenas ideas siempre y mostrando que no todo es tan complejo como parece y todo es posible.

A los amigos de la vida, de Viedma del gimnasio, de Muay Thai, imposible contarlos a todos. Todas buenas personas que siempre creyeron en mi, que siempre estuvieron ahí para ayudarme a hacer más ameno los momentos de esta etapa. Me ayudaron siempre a despejar mi cabeza cuando lo necesitaba. Me ayudaron a tener energías, a seguir, a levantar la guardia aunque estemos cansados, a respetar a la gente. Muchas gracias a todos ellos, me hicieron pasar momentos geniales y ayudaron a balancear lo profesional con lo personal.

Muchísimas gracias a Juanpi, que aunque la distancia hace imposible que compartamos momentos juntos, estuvo a mi lado siempre. Un gran mentor, un gran inspirador, una exelente persona, muy inteligente y siempre predispuesto. Siempre con energía, sabiendo guiar el camino. Infinitas gracias a él. Nunca me olvidaré todo el tiempo y ganas que me dedicó sin siquiera conocerme en persona.

A Javier Blanco, una de las primeras caras que vi cuando entré en Fa.M.A.F, que me mostró cosas fascinantes de manera sencilla, que me empezó a enseñar a pensar, que se mostró siempre como una persona ante todo, compartiendo sus conocimientos con los recién ingresados. Persona que ayuda siempre en la tarea tan díficil que es abrir las mentes y encantar a los futuros profesionales.

En el medio hay montones más de personas que estuvieron conmigo una y más veces, es imposible nombrarlos a todos. Pero el hecho de que no estén nombrados en estas palabras es meramente anecdótico ya que no los hace menos importantes porque siempre les voy a estar agradecido. Miles de gracias a los que creyeron y ayudaron, y a los que no también, porque de todos ustedes aprendí algo. 

Intentaré devolver todo lo que me dieron dando lo mejor de mi tanto en lo profesional como en lo personal.

Infinitas gracias a todos! 


\newpage
%
%Computers are incredibly fast, accurate, and stupid; humans
%are incredibly slow, inaccurate, and brilliant; together they
%are powerful beyond imagination - Albert Eintein
%
%

\clearpage
\thispagestyle{empty}
\mbox{}
\clearpage

\newpage
\section{• Motivación}
Los videojuegos de hoy en día constan de una calidad gráfica sin precedentes. Pero es bien conocido en la comunidad de los videojuegos la falta de inteligencia de los agentes autónomos y la falta de realismo o expresividad de los entornos dinámicos que se desean simular.

Supongamos que una persona juega a un \textit{First Person Shooter (FPS)} y al ingresar a un escenario se encuentra con uno o más enemigos dispuestos en determinada posición del escenario, estos reaccionarán de cierto modo al ver al jugador. Queremos evitar que el jugador sea capaz de aprender las reacciones de sus oponentes no humanos.
%Si la persona vuelve a jugar el mismo escenario varias veces es posible que aprenda los movimientos o reacciones de sus oponentes, si éstos no son otros jugadores humanos del videojuego.

Si los agentes del videojuego reaccionan de una forma predictiva ante una acción, entonces hay un claro déficit de inteligencia de dichos agentes. Aquí buscaremos evitar esas situaciones y obtener un comportamiento más libre y autónomo de los agentes.
%Por otro lado, se busca que si el jugador se quedara fuera de un escenario en el que se encuentran enemigos, entonces mientras éste no ingrese al escenario se desea que los enemigos tengan un movimiento libre. 
%Por lo tanto, la disposición de los enemigos en la habitación dependerá de cuando entremos y esta no será tan predecible. 
Pero cabe preguntarse: ¿Cómo darle libertad de movimiento a los actores sin que desarmen su grupo?, ¿Cómo hacer que trabajen en conjunto para lograr una meta?, ¿Quién controla o guía el grupo?, ¿Qué tan inteligente tiene que ser cada individuo para poder organizarse junto al resto?, ¿Cuán complejo debe ser un algoritmo para dar libertad y coherencia a los agentes?, ¿Hay una mente maestra atrás de todo eso?.

Estas son preguntas que han intrigado a los científicos por mucho tiempo. Craig Reynolds\footnote{\url{http://www.red3d.com/cwr/}} fue quién comenzó a dar solución a estas preguntas tratando de imitar comportamientos de la naturaleza. Todos hemos visto alguna vez bandadas de págaros volando, o cardúmenes de peces nadando, o incluso colonias de hormigas trabajando. Cada uno de estos grupos no son más que un conjunto de agentes de la misma especie que, sin mayor inteligencia, logran metas grupales que no podrían realizar de forma individual, como mejorar su modo de buscar comida, reconocer peligros, emigrar, etc. Para lograr esto es fundamental que logren agruparse de forma organizada.

Sin embargo, en los grupos mencionados no hay alguien responsable de organizar los movimientos o acciones a tomar en cada instante. Esto quiere decir que son grupos de agentes \textit{decentralizados}. También podemos notar que en estos grupos cada integrante solo es consciente de lo que pasa a su alrededor, i.e, \textit{tiene una imagen local de lo que sucede y no global}. Esto nos dice que un agente no guarda toda la información del grupo sino la suya y la de su alrededor. Otro punto que hay que tener en cuenta para los videojuegos es qué patrones queremos que tengan los agentes. Tener libertad de movimiento no implica carecer de un \textit{comportamiento} definido. Es por esto que también nos interesa poder predecir un determinado patrón de los agentes y saber si éste será estable o no.

Tratar de dar respuestas a estas preguntas es lo que motivó esta tesis. Poder aplicar técnicas que permitan \textit{simular} comportamientos de agentes y entornos fue una gran motivación. El hecho de lograr que emerga una organización en grupos que nos interesen, y donde no se les dice de forma directa como lograrlo. También fue motivación el pensar la amplia rama de aplicaciones que tienen temas como los que se tratarán aquí. Ya sea desde un videojuego hasta desarrollo de robots idénticos que se organizen para realizar alguna tarea en conjunto. Se cree firmemente que las ramas relacionadas a la IA seguirán siendo de gran crecimiento, acoplándose cada vez más con la industria y dando soluciones a la comunidad. Por eso aquí se intenta dar un pequeño aporte en ese sentido y fomentar su futuro estudio y aplicación.
\newpage

\section{• Introducción}

En el presente trabajo se estudiaron e implementaron técnicas de AI (Artificial Intelligence) y CA (Cellular Automata) enfocadas en el desarrollo de videojuegos. Se comenzó pensando en dar una solución computacional acorde a la industria de desarrollo de videojuegos, pero con más foco en la rama educativa. Primero se atacó el problema de dotar de cierta inteligencia a los agentes de los videojuegos. Dicho problema fue abordado mediante el uso de técnicas de \textit{flocking, swarm intelligence} para ser más específicos. Para esto explicaremos lo que es el flocking en la sección \ref{section-rebanio} y se seleccionan dos tipos de modelos que nos permiten desarrollar soluciones: \textit{modelos discretos} y \textit{modelos continuos}.

Se continúa el trabajo con el es\-tu\-dio e im\-ple\-men\-tación de téc\-ni\-cas de swarm in\-te\-lli\-gen\-ce ba\-sa\-das en modelos discretos y seguido a esto abordar la solución con modelos continuos. Se identifica la importancia de definir de forma clara la relación que habrá entre los agentes del sistema, pues será esta la encargada de hacer emerger un comportamiento grupal o no. Para los modelos discretos, que comienzan a tratarse en la sección \ref{section-modelos-discretos}, definiremos la interacción de los agentes haciendo uso de reglas del tipo ''si \textit{acción}, entonces \textit{reacción}". Se explica e implementa un flocking basado en las reglas de Craig Reynolds, al que luego se le aplican variantes. 

En la sección \ref{section-modelos-continuos}, se estudian e implementan técnicas de flocking basadas en modelos continuos. Aquí se decide abordar la solución haciendo uso de potenciales para simular la interacción de los agentes del videojuego. Se comenta la existencia de distintos tipos de potenciales y sus diferencias para luego elegir uno e implementar una solución con dicho potencial. Luego explicamos y mostramos la parametrización de dicho potencial. Para realizar esto se hicieron simulaciones basándose en un modelo continuo que luego se graficaron y analizaron off-line. También se muestra la emergencia de patrones y su convergencia o no.

%Dentro de los modelos continuos se decide abordar la solución haciendo uso de potenciales para simular la interacción de los agentes del videojuego. Se comenta la existencia de distintos tipos de potenciales y sus diferencias para luego elegir uno e implementar una solución con dicho potencial.

%Luego explicamos y mostramos la parametrización de dicho potencial. Para realizar esto se hicieron simulaciones basándose en un modelo continuo que luego se graficaron y analizaron off-line. También se muestra la emergencia de patrones y su convergencia o no.

%A continuación, se estudian e implementan técnicas de flocking basadas en modelos discretos. Aquí definiremos la interacción de los agentes haciendo uso de reglas del tipo ''si \textit{acción}, entonces \textit{reacción}". Se da comienzo con la explicación e implementación de un flocking basado en las reglas de Craig Reynolds, al que luego se le aplican variantes.%(separacion-sensores).

El estudio de las técnicas anteriormente mencionadas nos lleva a pensar en los agentes y su interacción con el medio. En los videojuego suele ser requisito que los agentes puedan \textit{sensar} algunas propiedades del entorno en el que se encuentran, tema que veremos en gran parte en la sección \ref{subsection-sensores}, que puede ser útil para la toma de decisiones. Con respecto a la toma de decisiones podemos pensar, por ejemplo, en que se requiera que un agente se acerque al calor o a la luz, entre otras tantas opciones. Pues bien, estas son propiedades dentro del entorno y el agente debe ser capaz de cuantificar estas propiedades para tomar buenas decisiones. Otro requisito puede ser que el entorno afecte al agente, como por ejemplo cuando sucede una explosión. Este tema también es abordado proponiendo técnicas de propagación en el medio. En particular se ataca el tema de propagación de presiones en el entorno, comenzando en la sección \ref{subsection-propagacion}. También en videojuegos se requiere que sea el agente quien afecte el entorno, ya sea entregando calor, sonido, destruyéndolo, etc. Veremos que con el prototipo de simulación que se propone, dichas acciones son simples de llevar a cabo. Para esto se abordó el problema de la simulación de \textit{entornos dinámicos}, problema bien conocido en la comunidad de los videojuegos.

Se propone, desde la sección \ref{subsubseccion-ca} una solución a dicho problema mediante el uso de autómatas celulares. Estos son ampliamente estudiados y conocidos por la comunidad académica. Explicamos sus características y cómo estas se adecuan a las necesidades que existen para simular entornos dinámicos. Mostramos un paradigma que permita simular escenarios y materiales complejos, y se implementa en la sección en la sección \ref{subsection-ca-implementacion} un prototipo de simulación que contenga las características anteriormente mensionadas. Luego, en la sección \ref{subsection-acoplamiento}, se integra a los agentes con dicho entorno y por último se hacen ejemplos de interacción entre los mismos.

%Como se vió un canal de comunicación en un sentido (sensores), también se pretende que exista la posibilidad de comunicación en el otro sentido. Estos canales son conocidos como \textit{actuadores} y su dirección es del agente hacia el entorno. Los agentes serán capaces de modificar o afectar el entorno modelado. Situación que será posible con una solución como la planteada aquí.

Ya sobre el final, secciones \ref{section-estado-del-arte} y \ref{section-conclusiones}, se hablará sobre ventajas y desventajas que se vieron en las soluciones planteadas. También se propondrá posible trabajo futuro y se elegirá un tipo de modelo que se cree más acorde para el desarrollo de videojuegos.

\newpage
\section{• Estado del Arte}\label{section-estado-del-arte}
Para cerrar este trabajo queremos destacar algunos temas o áreas de estudio actual y futuro que utilizan o donde puede aplicarze las técnicas aquí vistas. 

Hoy en día el swarm intelligence(SI) es un muy amplio campo de investigación. Las áreas donde se lo puede aplicar son numerosas debido a su robustes, su escalabilidad, su poder de reconfiguración, su tolerancia a fallas, su posiblilidad de administrar tareas en forma paralela. Por todas esas características y más es que la inteligencia de rebaño se puede aplicar, entre otras, en las siguiente áreas:
\begin{itemize}
\item Simulaciones de la naturaleza
\item Simulaciones de conductas sociales
\item Transportación
\item Búsqueda y Rescate
\item Detección de minas
\item Vigilancia y monitoreo
\item Servicios médicos
\item Aplicaciones militares
\item Juegos
\item Evacuaciones de gente
\item Analizar performance de Autopistas
%\item etc..
\end{itemize}

Sin embargo, hay dos áreas que claramente han dominado el campo de estudio. Las áreas son \textit{Optimización de Colonia de Hormigas}, del inglés \textit{Ant Colony Optimization (ACO)} y \textit{Optimización Combinatoria}, más conocida como \textit{Particle Swarm Optimization (PSO)}, y son algoritmos de optimización basados en el estudio del comportamiento de rebaños en la naturaleza. 

\textit{Ant Colony Optimization} es un algoritmo probabilístico que se basa en tratar de resolver problemas computacionales que se puedan reducir al comportamiento que tienen las hormigas para encontrar caminos óptimos desde su colonia hasta la comida. Un ejemplo de su aplicación es en el \textit{problema del viajante (Traveling Salesman Problem)}\cite{traveling-salesman-problem}, donde se ha usado de forma positiva \cite{salesman-problem}. Este problema está clasificado técnicamente como de solución en un tiempo no polinomial (NP-Hard). Un problema se considera NP-Hard cuando se demuestra que cualquier algoritmo de solución tiene un tiempo de ejecución que aumenta, en el peor de los casos, exponencialmente con el tamaño del problema.


Por otro lado, el algoritmo de \textit{Particle Swarm Optimization (PSO)}\cite{pso-def}\cite{pso-def2} es un método de optimización numérica que se basa en mantener soluciones o candidatos posibles, llamados partículas y mover éstas partículas en el espacio de búsqueda de la solución óptima siguiendo simples fórmulas para este movimiento. El comportamiento de las partículas se guía en base a la mejor solución encontrada en el espacio de búsqueda, que dicha solución se actualiza constantemente a medida que las partículas encuentran nuevas \textit{mejores soluciones}. 

Un ejemplo de aplicación de el algoritmo PSO es en el problema \textit{Secuenciamiento de Tareas} (Flowshop), que es un problema clásico de la programación de trabajos. La solución del modelo matemático consiste en encontrar una secuencia de tareas que emplee un tiempo mínimo de
procesamiento. Este problema también se considera NP-Hard, como el problema de \textit{Traveling Salesman Problem}.

Este último algoritmo (\textit{PSO}), atrajo la mayor de las atenciones en este último tiempo. La mayoría de los trabajos de investigación relacionadas a este algoritmo se basan en tratar de introducir variantes del mismo \cite{pso-paper1}\cite{pso-paper2}\cite{pso-paper3}\cite{pso-paper4}\cite{pso-paper5}\cite{pso-paper6}.

Otra de las aplicaciones de \textit{Swarm Intelligence} es en situaciones donde el problema se puede dividir en varias \textit{tareas paralelas} que se pueden resolver más eficientemente por un grupo independientes de agentes de las mismas características. Por otro lado, hay problemas donde se necesita agrupar a todos los agentes como una unidad y que trabajen de forma colectiva. Un ejemplo de esto son los sistemas multi-robots donde los robots se conectan fisicamente para alcanzar una tarea determinada. Podemos ver esto en \cite{multi-robots1}\cite{multi-robots2}\cite{multi-robots3}.

También se puede aplicar \textit{Swarm Intelligence} al campo de la exploración. Pensemos un instante en las misiones de la NASA a Marte como \textit{"Spirit and Opportunity"} donde se envió un vehículo explorador. Una mirada distinta sería enviar un grupo grande de vehículos independientes más pequeños y con menos inteligencia que se dediquen a explorar, siguiendo un algoritmo de exploración basado en \textit{Swarm Intelligence}. En el área de exploración podemos ver papers como \cite{exploration-bots1}\cite{exploration-bots2}.

\newpage
\section{• Metodología}
La \textit{Inteligencia de Rebaño} (del inglés Swarm Intelligence) es la propiedad de un sistema multi-agente, de hacer emerger una funcionalidad o patrón global de complejidad superior a la del grupo, donde éstos interactúan localmente entre sí y con el entorno. Aquí se supone un comportamiento idéntico para todos los agentes de un grupo. Esto quiere decir, que el algoritmo o controlador que define su comportamiento será común a todos, sin la existencia de agentes que se destaquen sobre otros. 

También se supone en estos sistemas que sus integrantes son de una inteligencia limitada, como es el caso de hormigas o peces en la naturaleza. Este punto es el que da mayor relevancia a la inteligencia de rebaño, ya que nos posibilita aplicarlo en agentes de videojuegos o robots(\textit{boids}), puesto que los mismos carecen de inteligencia o tienen una una inteligencia limitada. Este paradigma intenta resolver cómo un grupo numeroso de agentes puede interctuar, de forma local y descentralizada, para provocar la emergencia de un sistema colectivo e inteligente. Esperaríamos que un sistema como el planteado conste de ventajas inherentes al mismo, como \textit{robustes, flexibilidad y escalabilidad}.

La \textit{robustes}, es la capacidad de un sistema de tolerar o sobreponerse a defectos, variaciones, ataques maliciosos, etc. Es una propiedad que debe ser implicada por el diseño del sistema y no por agregados a módulos que se consideran sensible. Hoy en día es una propiedad requerida de cualquier sistema complejo.

Con swarm intelligence, esta propiedad es consecuencia de sus atributos. Tenemos un sistema redundante en cuanto a los problemas no deseados que pueden ocurrir con algunos agentes o con pérdidas de los mismos, ya que al ser todos idénticos, la pérdida de agentes es compensable y de no compensarse, dicha pérdida se espera que no afecte considerablemente el funcionamiento del sistema en sí, hasta cierto nivel. También la descentralización del sistema nos indica que al no depender de alguien específico el conocimiento o control del sistema, si se afecta una de sus partes entonces no se estará afectado su totalidad. No hay un centro de control. 

% POTENCIALIDAD DE AGENTES, CON AGENTES SIMPLES SE LOGRAR COSAS MAS COMPLEJAS
%Luego, nos queda destacar la simplicidad de cada agente, puesto que ninguno de ellos debe concentrar inteligencia o conocimientos vitales para el sistema.% Distinto a si se concentra demasiada complejidad en cada uno de ellos para lograr que se organicen.

La \textit{flexibilidad}, es la capacidad de un sistema a actuar de diferentes maneras frente a una situación. Esto no implica falta de especificación del sistema, sino responder a reglas más generales con libertad de acción. En grupos de agentes idénticos no se pretende que uno asuma la plena responsabilidad de una acción. En los videojuegos sería que agentes con características o roles similares cumplan funciones similares. Esta característica brinda una amplia libertad e inteligencia a los videojuegos ya que implica que un agente puede cumplir distintas tareas según crea necesario y no debe crearse especificamente para el cumplimiento de una sola tarea. Pero cuando o como cumplir dichas tareas no necesita ser especificado por el desarrollador. De este modo ganamos un punto importante en el desarrollo de videojuegos, que es evitar la predicción de comportamientos de los agentes. Esto da una sensación más realista al videojuego y ayuda a mejorar la inmersión del usuario en el videojuego. Esta propiedad se destaca en los modelos de tipo continuo más que en los de tipo discreto, ya que los últimos son modelos basados en la aplicación de reglas que suelen definirse de forma deterministica. Aunque destacamos que a los modelos continuos se les puede asociar una probabilidad de aplicación a cada regla.

La \textit{escalabilidad}, es la capacidad del sistema de conservar su performance sin verse afectado por la cantidad de agentes. Esto es más que deseable en los videojuegos, sobre todo en los relacionados a estategias donde hay varios grupos de agentes con numerosos integrantes. Situación que se da habitualmente en videojuegos de guerra o batallas, donde los batallones que se enfrentan pueden contar de cientos de hombre. Estos hombres a su vez pueden pertencer a distintos grupos, organizados por algún criterio, como armas o skill. 
%que se puede querer que se organizen según el arma de ataque que usen.

Gracias a las técnicas de swarm intelligence los agentes seguirán regidos por algoritmos que se basan en su entorno local, dejando de lado lo que sucede globalmente. Dicha descentralización nos permite desarrollar técnicas simples de coordinación y estrategia. Cada uno será autónomo, en el sentido que su comportamiento no se basará en un administrador o mastermind global, sino que él mismo decidirá su comportamiento, por lo que se espera que un aumento en cantidades de agentes no impacte directamente en su performance, como si lo haría con un sistema centralizado ya que debe mantener toda la información del mismo. Luego un sistema como el planteado aumenta su complejidad de forma lineal y no exponencial como un sistema centralizado.
%%%% CONTINUACION 17/DIC 
%%%% posibilidades para seguir: contar que estas propiedades que tienen las tecnicas de SI hacen que sean aplicables a una gran cantidad de problemas (quizá nombrar algunos y dar referencias). Pero no olvidar de comentar que una rama donde se propone fuertemente el uso es en videojuegos. Contar también los distintos tipos de algoritmos para lograr swarming, que se implementaron de dos tipos, las elecciones que se tomaron. Que se cree más util utilizar en videojuegos, por qué(o se puede dejar para las conclusiones)

Las propiedades antes mencionadas destacan la amplia gama de aplicación que tienen los algoritmos de swarm intelligence. Una de las aplicaciones en la que nos concentramos es en la de videojuegos ya que creemos firmemente que estas técnicas pueden ayudar tanto a la simplificación del desarrollo, como a la mejora de la experiencia de jugabilidad del usuario. Para alcanzar estos resultados, se pueden usar diversos tipos de algoritmos. Entre ellos destacamos el uso de algoritmos basados en modelos de tipo continuo y discreto. Aquí se estudiaron e implementaron ambas soluciones.

La propuesta que hacemos no debería sonarnos distante ya que a menudo vemos en la naturaleza como se forman grupos y estos se mueven realizando varios patrones complejos. También observamos la capacidad de escalabilidad que tienen, ya que se observan grupos de todos los tamaños. Sabemos que los agentes de un sistema como el planteado no cooperan directamente con la formación del grupo, porque no tienen la información de que patrón formar o cual es su papel en dicha formación. Más aún, si un agente realiza lo que podemos pensar como un mal movimiento dentro de la formación del grupo o bien se aleja, el resto no tiene la inteligencia necesaria para comprender cómo esa acción afecta a la formación del grupo y de qué manera compensarla.

En la naturaleza, la información que tienen los agentes para saber cómo deben reaccionar proviene en general de su ADN. Es ahí donde tienen escritas las reglas a seguir, y estas son tan básicas como saber que se tienen que mover en grupo, segui el grupo,  localizar comida, evitar el peligro, etc. Estas reglas simples son las que rigen su vida, junto con toda la información que puedan sensar en un momento particular. Por ejemplo: saben que deben moverse en grupo por lo tanto si un ave se encuentra sola y tiene un grupo de aves de su especie cerca, ésta tratará de unirse al grupo y moverse en el sentido que tiene el grupo, pero si para hacer ese movimiento tiene que atravezar un peligro, como algún predador, entonces es muy probable que, de poder sensar ese peligro, interrumpa su movimiento tratando de alejarse del peligro. Esto nos dice que dentro del conjunto de reglas, hay algunas que podemos querer priorizar. En particular, son las reglas asociadas a la supervivencia las que suelen tener mayor prioridad, seguidas por un conjunto de reglas más generales. Recordemos que las especies lo que tratan de lograr es la evolución, y sin supervivencia no hay evolución.

No debemos perder de vista que es de nuestro interés poder actuar de una manera similar en los videojuego. Pensemos en un juego de rol con muchos personajes extra, aquí nos gustaría que con el pasar del tiempo los agentes simulados por algoritmos comienzen a organizarse y \textit{aprendan}. Por ejemplo, si se requiere juntar algún material cada agente puede tener un grado de felicidad por el tiempo que tardó en encontrarlo y la calidad del mismo, esto puede consultarse entre agentes de forma que cuando alguien encuentre un buen camino hacia el material deseado se lo comunique a los agentes de su entorno que le preguntarán. Lo que buscamos es que cada grupo de agentes tienda a quedarse con la mejor solución encontrada entre ellos, que se mantendrá hasta que se relacionen con más agentes y encuentren una mejor solución en conjunto.

Para llegar a estos objetivos es vital la \textit{información}. La información y las decisiones tomadas en base a ella es lo que dirá qué grupos evolucionan y qué grupos no. Aquí es donde toma mayor importancia moverse en grupo y podemos ver las ventajas de la inteligencia de rebaño. Si un grupo de agentes logra organizarse, entonces éste dispondrá y se comportará de acuerdo a una información que es mayor y más rica que la que dispone cada agente en particular de dicho grupo. Información como la ubicación de la comida, evitar peligro, rutas para migrar, etc. 

Por lo tanto, no es necesario que cada agente en particular tenga toda la información que tiene el grupo como unidad para favorecerse de ella. Esta información e inteligencia \textit{emerge} del grupo y a la vez no está localizada en ningún agente en particular sino en la suma de ellos, de pequeña información, ya sea erronea o no. No es necesario que cada agente tenga la mejor información, o que esta sea certera, ya que será trabajo del grupo el poder compensar ese dato con el del resto de los agentes. Acción que terminará por favorecer incluso al agente con mala o escasa información. En la naturaleza esto se ve de forma muy clara, para un animal que se separe de su grupo sus probabilidades de supervivencia y evolución son mucho menores a que si éste se hubiera quedado con su rebaño.

\newpage
\subsection{• Algoritmos de Rebaño}\label{section-rebanio}
%Dentro de swarm intelligence hay varias ramas de aplicación y estudio, desde video juegos hasta exploración de superficies. Pero dentro de estas ramas de aplicación, también podemos encontrar 
%Hay distintos algoritmos capaces de generan la inteligencia de rebaño. Dichos algoritmos son conocidos como \textit{algoritmos de rebaño (flocking algorithms)}. 
Los \textit{algoritmos de rebaño (flocking algorithms)} podemos definirlos como el motor de un sistema distribuido multi-agente, ya que serán los encargados de guiar al agente en su movimiento. En \cite{sof-vs-hard-core} se define \textit{flock} como \textit{el movimiento coherente de un grupo de partículas auto-propulsadas que emerge de un conjunto de interacciones entre las partículas del grupo}. Esta auto-gerenciación y cooperación de los agentes del sistema depende de los tipos de algoritmos y modelos elegidos. Identificaremos y analizaremos dos tipos distintos de algoritmos de rebaño: \textit{algoritmos basados en un modelo continuo y algoritmos basados en un modelo discreto}. Vale aclarar que aquí nos centraremos en sistemas donde los agentes tengan un concepto de espacio y puedan moverse en él de forma autónoma. %También existen híbridos de estos algoritmos, conocidos como \textit{algoritmos mixtos}.

Dentro de los modelos continuos, podemos encontrar algoritmos que se basan en potenciales de interacción conocidos, como los potenciales de Morse\cite{morse1}\cite{morse2}, Lennard-Jones\cite{L-J-1}\cite{L-J-2} y Van der Waals\cite{van-der-waals1}. Dichos potenciales son conocidos por su uso en modelos de interacción molecular. Aquí haremos una abstración necesaria, la cual consiste en suponer a nuestros agentes como las moléculas para las que fueron definidos los potenciales. Luego, los potenciales pasaran a definir la interacción entre un par de agentes del sistema y no más entre moléculas. Por lo tanto, de aquí en adelante, el potencial que elijamos será el encargado de defir como se relacionarán los agentes entre si. 

%Una vez elegido el potencial a usar en el algoritmo de rebaño, debemos definir el comportamiento de los agentes dentro del sistema. En este tipo de algoritmos, los agentes basan su comportamiento en ecuaciones de movimientos que serán modificadas por fuerzas. Donde la fuerza que caracterizará el comportamiento de cada agente viene definida por el gradiente del potencial elegido. En general, los potenciales usados suelen estar compuestos por dos componentos principales: \textit{de atracción} y \textit{de repulsión}. También vale aclarar que aquí veremos potenciales conocidos como \textit{potenciales de a pares (pairwise potencials)}, lo que implica que la fuerza resultante calculada por el agente $i$ hacia el agente $j$ será la misma misma que la fuerza calculada por el agente $j$ hacia el agente $i$, cualesquiera que sean los agentes $i$ y $j$.

Por otro lado, tenemos los modelos de tipo discretos, donde veremos algoritmos basados en reglas genéricas, del tipo \textit{no chocar, acercarse a los vecinos, etc}. En estos algoritmos se tiene un conjunto de reglas que intenta definir el comportamiento global haciendo uso de la interacción entre los agentes, que será el resultado de aplicar las reglas. Como algunas reglas pueden generar conflicto con otras, como en el caso de \textit{evitar colisiones} y \textit{agruparse} con sus vecinos, las reglas podrán tener una noción de prioridad. Dicha prioridad se suele aplicar usando un órden para las reglas o el grado de aplicación de la misma. Aquí vemos la noción de determinismo que hace notar que la flexibilidad del sistema no se mantiene total. Los distintos comportamientos dependerán de las condiciones que tengan de aplicación cada regla y lo sensado por cada agente de forma local en cada instante. Esto incluye sus estados internos y los del entorno.

\newpage
\subsection{• Modelos Discretos}\label{section-modelos-discretos}

%Ya vimos un tipo de modelo de simulación, de tipo continuo, ahora hablaremos sobre los modelos de tipo discreto. 
Dentro de este tipo de modelos nos centraremos en los que definen la interacción de sus agentes en base a reglas. La meta aquí es también lograr la coordinación, organización, cooperación y autogerenciamiento de grupos de agentes sin perder su comportamiento individual y definido. Veremos que se puede lograr un comportamiento sofisticado haciendo uso de reglas simples que definan la semántica del comportamiento de cada individuo pero de forma genérica, ya que se aplicarán por igual a todos los agentes de un grupo. Reglas como \textit{''buscar comida"} y \textit{''evitar choques"}. Sin embargo, se pueden definir varios grupos distintos, cada cuál con su conjunto de reglas que definirá su futuro comportamiento. 

Esperamos que una buena elección de reglas genéricas nos permitan definir no solo el comportamiento individual de los agentes de nuestro videojuego sino también el comportamiento grupal emergente de sus interacciones locales. A estas reglas las vincularemos con acciones fundamentales de los mismos, como movilidad y roles. Por ejemplo, podemos pensar en un videojuego donde ocurran batallas y nuestro rebaño sea un batallón. Estos pueden comenzar con un rol de ataque o emboscada, y dependiendo de su entorno local pueden cambiar a otros roles. Si logran derrotar a su enemigo pasarán, por ejemplo, a un rol de exploración, mientras que si número de vecinos o compañeros de batalla se reduce más de una determinada cantidad, entonces lo considerarán una derrota y pasarán al rol de huida. Dichos cambios de roles dependerán de lo sensado por el agente en su entorno local en un momento dado y la prioridad y parametrización de las reglas.

%Hay que destacar la libertad de acción que tendrán los agentes del videojuego. 
%Una definición de reglas genéricas como las aquí planteadas nos permitirán no tener que codificar de que forma tienen que reaccionar ante cada situación en la que se encuentren nuestros agentes. Luego, tendremos agentes que sepan como responder a situaciones no previamente definidas, situaciones que surjan o emerjan de la mera evolución del juego o simulación, dando una mayor libertad de acción y simplificando la escritura de los controladores de dichos agentes. 

%en un momento nuestros agentes dentro del juego pueden tener un rol de exploradores, luego pueden necesitar pasar a un rol defensivo o de reorganización. Dichos cambios de roles dependerán de lo sensado por el agente en su entorno local en un momento dado y la prioridad y parametrización de las reglas. Un agente autónomo puede tener por regla moverse en grupo, siempre y cuando no sienta peligro, entonces cuando se genere una situación de peligro su rol puede cambiar a huir del mismo, dejando claramente el rol de organización en grupo.

Las acciones que toman los agentes pueden ser en base a metas o goles definidos por el animador, otras acciones pueden definirse en base a reacciones a eventos del entorno dinámico (como alejarse del calor), también pueden basarse en necesidades de los mismos (como energía) y pueden tomarse acciones preventivas en base a aprovechar oportunidades en las que se encuentren los agentes, y por último algunas acciones pueden ser aleatorias y ejecutarse o no según alguna probabilidad que se desea mantener por debajo de la regla (como atacar). Este tipo de acciones acopladas a un conjunto de reglas pueden llevar a los agentes a comportarse de una forma suave, con mayor realismo y libertad. Hay que destacar que al carecer de reglas claras para la definición del comportamiento de distintos grupos de agentes, el desarrollador deberá customizar muchar variables, como distancias mínimas, grado de aplicación de las acciones, etc. Es por esto que vemos como buena práctica usar otros estudios, ya sea de tipo biológico o social para intentar rescatar el comportamiento de los agentes que deseamos simular.

Aquí hay dos tipos principales de metas que se pueden perseguir al de\-sa\-rro\-llar un videojuego donde actúan rebaños o grupos de agentes. Una de las metas es lograr una simulación en tiempo real, donde no es importante el comportamiento exacto de cada agentes sino que es el grupo de agentes el que debe tener un comportamiento realista. Otra de las metas es que cada individuo siga un comportamiento más realista, pero esto implica mayor complejidad en el algoritmo que simula su inteligencia y capacidad cognitiva. Por lo que en este tipo de casos, tener un modelado de tiempo real es factible para grupos más reducidos. En el presente trabajo nos inclinaremos por las metas del primer tipo.

Los modelos basados en reglas fueron introducidos por Craig Reynolds en 1987. En este modelo, los integrantes son representados como agentes orientados con un sistema de control de reglas definido. Cada agente es implementado como autónomo, cuyo movimiento se basa en su percepción local del entorno dinámico en el que se encuentra y el conjunto de reglas que definen su comportamiento, junto con la aplicación de ecuaciones de movimientos basadas en la física. %El comportamiento final será el emergente de las características mencionadas junto a la interacción con otros agentes y la evolución del medio.

Las reglas del modelo introducido por Reynolds son: \textit{alineación, separación y cohesión}. Con estas simples reglas se puede crear un algoritmo de rebaño en donde los agentes del sistema se auto-organicen. Estas reglas permitirán alcanzar un requisito que suele ser fundamental en todo videojuego donde se pretende que grandes grupos de agentes se muevan de forma autónoma, este requisito es la variabilidad de movimiento de los agentes de nuestro sistema en los entornos. Queremos evitar que todos los agentes tengan un movimiento idéntico a lo largo del tiempo, esto claramente es anti-realístico y afecta la jugabilidad e inmersión del usuario, quitanto toda posible inteligencia de los agentes. Dicha variabilidad requerida será inherente a nuestro modelo basado en reglas, ya que se desprende de la generalidad de las mismas. Vale aclarar que suele ser imposible contemplar los distintos estados que un videojuego puede tomar y que si bien siempre se intentará desarrollar de forma abstracta, aquí se muestra otro paradigma que intenta ayudar en este sentido.

Nuestros agentes, si bien se pretenden sean autónomos en cuanto a su movimiento en el entorno, también tendrán la capacidad de coordinarse, colaborar, e inclusive competir con otros agentes. Los agentes serán capaces de elegir que tipo de tarea realizar, cambiando según el estado del entorno local y los agentes vecinos. Por algún momento se puede requerir acoplarse con agentes y en otros se puede necesitar alejarse, ya sea por evitar colisiones o algún peligro. De esta forma, podemos ganar realismo en las escenas de un videojuego. Sobre la colaboración y coordinación entre agentes simulados hay trabajos realizados como \cite{Shao2005}, \cite{pelechano2006} y \cite{Yu2007}, y la individualidad alcanzada por los agentes también ha sido foco de trabajos de investigación como \cite{MusseThalmann}, \cite{PelechanoCrowdsimulation}, \cite{PelechanoBuildingEvacuation}, \cite{DurupinarCrowdVariation}.

%Autonomy may be extended to include mechanisms for characters to coordinate, collaborate, and even compete with other agents. The characters would themselves decide when a task requires additional personnel and schedule appropriately. Individuality makes crowd scenes more interesting and realistic. Also important is the formation of groups. People have affiliations with others that change over time and even during the course of a day. In scenarios with larger numbers of virtual humans, these dynamic changes become important for realism.

En los modelos como el planteado se requerirá entonces que los agentes sean capaces de percibir el entorno local y poder reaccionar ante los cambios sensados. Para la simulación de la percepción de agentes de videojuego es que se desarrollan distintos tipos de sensores, los cuales serán consultados desde el controlador de cada agente para luego poder tomar una decisión en base a sus valores. En este trabajo se proponen dos tipos de sensores, un tipo será basado en visibilidad geométrica y el otro será de sensores basados en propagación en el medio.

Los sensores de visión estarán a cargo de identificar el conjunto de agentes vecino, posiciones de los mismos y distancias, como la distancia al más cercano, para impedir que ocurran colisiones. Mientras que los sensores de propagación en el medio serán los que se conectarán con el entorno dinámico para permitirnos medir cierta propiedad del medio que nos interese, como presión o temperatura. Algunos trabajos basado en sensores pueden encontrarse en \cite{Shao05environmentalmodeling} y Massive SW \cite{massiveInc}, usado en la película El Señor de los Anillos, utiliza un sistema de simulaciones donde el comportamiento de los agentes está basado en visibilidad.

Por simplicidad se decidió utilizar un modelo en dos dimensiones. Los agentes no tendrán restricciones para moverse en el mismo, simplemente deberán seguir todos el mismo conjunto de reglas. Comenzarán en posiciones iniciales aleatorias y luego comenzarán a aplicar todos sus reglas, de forma paralela. Para realizar la primera implementación de un modelo como el planteado se decidió utilizar NetLogo\cite{netlogo}, una herramienta bien conocida en el mundo de simulaciones de sistemas multiagentes. Veremos esta herramienta con mayor detalle más adelante, en la sección \ref{sectionNetLogo}, pero antes hablaremos de las reglas de un controlador como el planteado.

\subsubsection{• Reglas}\label{reglas-subsection}
%Así como se eligió un potencial que defina la relación entre agentes para algoritmos continuos, también debemos definir un conjunto de reglas para el estudio de algoritmos discretos.

%In the mid 80's Craig Reynolds applied the principles of A-life to the phenomenon of birds flying in coordinated flocks. The challenge was to uncover simple rules that each bird (or boid) could follow that would produce flocking as an emergent behavior. Flocking is not a quality of any individual bird; it only emerges as a property of a group of birds. Each bird acts as an independent Agent and obeys the simple rules. Reynolds identified three simple rules for each boid to follow within some given global parameters, and the result was an uncanny facsimile of flocking behavior unfolding itself on his computer screen. The phenomenon has been applied repeatedly on screen in SIGGRAPH animations, for the penguins in Batman and the Wildebeest stampede in Lion King. To see the Java code behind boid

Vale aclarar que las reglas se deben ajustar a distintos tipos de rebaños. No seguirán las mismas reglas una colonia de hormigas y una bandada de pájaros. Las reglas que aquí se decidieron usar son 3: \textit{alineación, separación y cohesión}. Con estas simples reglas se puede crear un algoritmo de rebaño en donde los agentes del sistema se auto-organicen. Pasemos a explicar las reglas elegidas.

\begin{itemize}
\item \textbf{Separación:} Significa que los agentes tratarán de evitar choques o aproximaciones muy cercanas a otros agentes. Mientras más cerca están los agentes más aumenta la fuerza repulsiva entre ellos.

\item \textbf{Co\-he\-sión:} Sig\-ni\-fi\-ca que los a\-gen\-tes ten\-de\-rán a mo\-ver\-se ha\-cia otros agentes cercanos. Los agentes no quieren estar lejos de sus vecinos.

\item \textbf{Alineación:} Significa que los agentes ten\-de\-rán a mo\-ver\-se en el mismo sentido en que se mueven los agentes a su alrededor.
\end{itemize}

%Velocity is a vector quantity, referring to the combination of heading and speed. The manner in which the results from each of these behaviors is reconciled and combined is significant and is discussed in more detail later. Similarly,the meaning nearby in these rules is key to the flocking process. This is also discussed in more detail later, but generally one boid's awareness of another is based on the distance and direction of the offset vector between them.


La \textit{alineación} y la \textit{separación} son reglas complementarias. Una reorienta al agente mientras la otra lo aleja de una posible colisión con un vecino. Juntas permiten que los miembros de un rebaño puedan moverse libremente evitando colisiones, aún estando sobre populado de agentes. La separación es la necesidad de alejarse de un posible impacto. La separación estática se basa en la posición relativa de los vecinos e ignora completamente su velocidad y dirección. Por otro lado, la alineación se basa solo en la dirección en la que se mueven los vecinos e ignora completamente sus posiciones. Aquí vemos como se complementan ambas reglas. Pero la alineación, a su vez, se puede ver como una forma predictiva de evitar colisiones ya que si un agente logra una buena alineación con sus vecinos, entonces es poco probable que colisione con alguno de ellos. La alineación hará que la distancia entre vecinos tienda a mantenerse dentro de un rango fijo. Luego, la separación estática sirve para establecer un mínimo de distancia requerido para el sistema, mientras que la alineación tiende a mantenerlo.

La \textit{cohesión} es la regla que hace que los agentes quieran acercarse a otros agentes. Pero al tener una percepción local del sistema, acercarse a otros implica juntarse con sus vecinos cercanos. Esta regla hace que se quieran mover hacia el centro de masa de su grupo de vecinos. Por lo tanto, si se encuentran cerca del centro del grupo y junto a muchos vecinos, se encontrará muy cerca del centro de masa de su rebaño y por ende la necesidad de moverse hacia el centro será mínima. Pero si se encuentran en los límites externos del rebaño entonces tendrá una necesidad mayor de moverce hacia el centro de masa del rebaño por lo que se notará más el cambio de direccionamiento en su movimiento.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm]{img/vecinos.eps} 
}
\caption{Vecinos de un agente. Vecinos de $i_0 = \lbrace i_1, ..., i_6\rbrace$. Vecinos de $i_6 = \lbrace i_0, i_1, i_4, i_5\rbrace$.}
\label{vecinos}
\end{figure}

Con estas reglas se puede crear un algoritmo de rebaño que simule por ejemplo una bandada de pájaros, un cardumen de peces u otro conjunto de agentes de nuestro videojuego. Los agentes del sistema deberán ser capaces de acceder a su estado interno y también al estado local del sistema. Pues solo hará falta estos datos para que el sistema se organice, eh aquí la emergencia de inteligencia del rebaño. También será de vital importancia para nuestro algoritmo definir o poder identificar un conjunto de agentes cercanos, referenciados anteriormente como \textit{vecinos} y, a su vez, vamos a necesitar identificar dentro del conjunto de \textit{vecinos} al \textit{vecino} más cercano que tengamos, esto es para que podamos evitar colisiones aplicando la regla de \textit{Separación}.

Hasta aquí, nuestros algoritmo se basa en los vecinos de cada agente y el vecino más cercano para poder identificar que acción tomar en un caso determinado. En este tipo de algoritmos se puede dar el caso que alguna regla no sea compatible con otra, como sucede con \textit{separación y cohesión}. Mientras que la regla de \textit{Cohesión} dice que se tienen que acercar a sus vecinos, en algunas ocasiones la regla de \textit{Separación} dirá lo contrario. Es, por lo tanto, necesario que nuestro algoritmo tenga en cuenta estas situaciones y para ello se deberá definir una prioridad que dirá que regla aplicar en situaciones de conflicto o bien resuelve de modo probabilístico. Aquí se considera como prioridad \textit{evitar colisiones}, por eso, cuando se acerquen demasiado, la regla que se aplicará es la de \textit{separación}, dejando de lado las otras dos reglas. El algoritmo se puede implementar de la siguiente manera:

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm]{img/aplicar-reglas.eps} 
}
\caption{Algoritmo de aplicación de reglas.}
\label{aplicar-reglas}
\end{figure}

\begin{enumerate}
\item Obtener vecinos (agentes que se encuentran en un radio de distancia $x$ )
\item Obtener el vecino más cercano. El agente más cerca del grupo obtenido en el punto anterior, si es distinto de vacío.
\item Pregunto si el vecino más cercano está muy cerca(menor a la distancia definida de separación)
\begin{itemize}
\item Si, entonces aplico solo la regla \textit{Separación}.
\item No, entonces aplico primero \textit{Alineación} y luego \textit{Cohesión}.
\end{itemize}


\end{enumerate}

Daremos a continuación una implementación del algoritmo propuesto arriba con la herramienta NetLogo.


\newpage
\subsubsection{• Netlogo}
\label{sectionNetLogo}

Netlogo\cite{netlogo} brinda un ambiente programable para poder simular fenómenos tanto sociales como naturales. Para simular sistemas, el lenguaje nos ofrece dos objetos: \textbf{\textit{turtles}} y \textit{\textbf{patches}}. A diferencia de la mayoría de los lenguajes orientados a objetos, el usuario no puede definir los objetos que quiera, sino que debe usar los ofrecidos por el lenguaje. 

Algo especialmente interesante sobre Netlogo es que permite dar instrucciones a sus objetos de forma concurrente. Facilitando la simulación y estudio de sistemas de interacción masiva y paralela, lo cual es caso de los sistemas de rebaño.

Tanto las \textit{turtles} como los \textit{patches} pueden recibir instrucciones. Estas instrucciones se dan escribiendo \textit{procesos} y a su vez un conjunto de estos procesos es lo que constituye y define un programa de Netlogo. Los procesos pueden ser de dos tipos: \textit{procesos de turtles} y \textit{procesos del observador}. Los procesos de las turtles son el conjunto de instrucciones llevadas a cabo por las éstas, de forma paralela. En uno de estos procesos, una turtle puede pedirle a un patch que ejecute cierto comando, como por ejemplo, pedir al patch en donde esa turtle está ubicada que actualize su estado a un nuevo valor.

Por otro lado, un proceso del \textit{observador} nos permite desde inicializar el programa hasta recolectar datos. Este tipo de procesos le puede pedir tanto a las turtles como a los patches que ejecuten comandos. Desde este tipo de procesos también se pueden crear o eliminar turtles, definir los patches que se usarán y monitoriar el estado de las mismas.

Lo que se hace con este lenguaje para obtener una simulación es definir el tamaño del sistema, lo cual definirá los patches usados. También se deben crear la cantidad de turtles que creamos necesarias, que representan a los agentes del sistema. Luego hay que crear procesos que representen las reglas que deseamos que los agentes cumplan, como por ejemplo un proceso de \textit{alineación}, otro de \textit{separación} y otro de \textit{cohesión}. Así como también serán necesrios otros procesos auxiliares, para calcular el conjunto de vecinos de una turtle dada y el vecino o turtle más cercano para cada turtle. Tendremos también algún proceso del tipo observador que inicialize el sistema y les pida a las turtles de forma paralela que ejecuten los procesos definidos para satisfacer las reglas en el orden que creamos necesario.

Con esta herramienta se logró reproducir un comportamiento de flocking, siguiendo el siguiente algoritmo.

\begin{mylisting}
\begin{verbatim}
to flock  ;; procedure de turtles
  find-flockmates	;; busco vecinos
  if any? flockmates	;; si tengo vecinos	
    [ find-nearest-neighbor	;; busco la distancia al mas cercano
      ifelse distance nearest-neighbor < minimum-separation
        [ separate ]	;; si distancia menor a distancia minima aplico separacion
        [ align			;; sino, aplico alineacion y cohesion
          cohere ] ]
end
\end{verbatim}
\end{mylisting}

Como podemos notar, este algoritmo refleja de forma casi idéntica el planteado sobre el final de la sección \ref{reglas-subsection}. Este algoritmo será ejecutado por cada turtle en paralelo en cada tick de tiempo. Lo primero que entonces cada turtle es buscar a sus vecinos, y esto lo hace con el siguiente proceso.

\begin{mylisting}
\begin{verbatim}
to find-flockmates  ;; turtle procedure
  set flockmates in-2cone2 50 280 45 45 vision
end

to-report in-2cone2 [ degree1 degree2  ampl1 ampl2 r ]
;; devuelve las turtles que se encuentran en el cono de radio r y amplitud degree2 
;; que esta a degree1 grados de la turtle que lo llama
  let  mates other turtles in-radius r ;; tengo los vecinos en el radio de mi vision
  let return mates with [ ((atan xcor ycor) >= (degree1 - (ampl1 / 2.0) )mod 360 and 
                     (atan xcor ycor) <= (degree1 + (ampl2 / 2.0) )mod 360 )or (
                     (atan xcor ycor) >= (degree2 - (ampl2 / 2.0) )mod 360 and 
                     (atan xcor ycor) <= (degree2 + (ampl2 / 2.0) )mod 360)
                     ]
  report return  
end

\end{verbatim}
\end{mylisting}

Aquí definimos a los vecinos como todas las turtles que se encuentren en un cono de radio y amplitud previamente seteada por el usuario. Este procedimiento intenta simular la \textit{visión} de cada turtle. Por último queda mostrar la implementación de las reglas de separación, alineación y cohesión. Estas definen el comportamiento de cada turtle y se pueden implementar de la siguiente manera.

\begin{mylisting}
\begin{verbatim}
to separate  ;; procedure de turtles
  turn-away ([heading] of nearest-neighbor) max-separate-turn
end

to align  ;; procedure de turtles
  turn-towards average-flockmate-heading max-align-turn
end

to cohere  ;; procedure de turtles
  turn-towards average-heading-towards-flockmates max-cohere-turn
end
\end{verbatim}
\end{mylisting}

Algo nuevo dentro de la implementación recién vista es el uso de sensores. En este caso son vitales para nuestro algoritmo ya que las decisiones de aplicación de reglas se toma estrictamente en base a los resultados devueltos por los mismos. Aquí se implementó un sensor basado en visón y en particular un sensor de visión en cono, podemos ver un ejemplo de ejecución en la Figura \ref{netLogo-simultaion1}. El tema de sensores es otro punto de interés en nuestro trajo y merece la pena una sección aparte.

\newpage
\subsection{• Modelos Continuos}\label{section-modelos-continuos}

La auto-organización de agentes es un área de estudio muy interesante \cite{morse1} \cite{morse2}, que llega cada vez con más fuerza a la industria de los videojuegos. La posibilidad de un autogerenciamiento de grupos de agentes permite escalar los juegos sin el peligro de la perdida total del realismo. Aqui aparecen ventajas como más y nuevas interacciones para el usuario y la posibilidad de desarrollar en el juego una historia que se adapte a las decidiones del jugador. Situación no usual hoy en día, ya que el usuario en muchos casos tiene un itinerario de acciones a seguir para cumplir el desarrollo del juego dentro de ciertos parámetros acotados previamente definido. %Por lo tanto, muchas de estas soluciones son de utilidad en el desarrollo de videojuegos, sobre todo en el desarrollo de controladores para el comportamientos de distintos grupos de agentes. Ya sea que estos agentes se basen en simular comportamientos de personas, animales, naves, etc. 

%Aquí nos alinearemos con la rama de estudios que intenta predecir patrones y estabilidad en sistemas de rebaño. 
%Deseamos saber de que forma afectará a los agentes la elección y parametrización del potencial elegido para nuestro modelo. Habrá distintas parametrizaciones para cada modelo, Queremos ser capaces de desarrollar un controlador para los agentes que nos permita saber de antemano el \textit{comportamiento} que tendrán.
%Otra razón de interés para el estudio de swarm intelligence es la necesidad de entender como los rebaños y la interacción entre agentes en la naturaleza ayuda a estos grupos a alcanzar  sus varias metas, entender como evoluciona el comportamiento de un rebaño y su autogerenciamiento. 

%En particular, los algoritmos basados en swarm intelligence proveen nuevas formas de resolver problemas de optimización complejos, de administrar y controlar el tráfico y redes de comunicación, lograr formas efectivas de generar simulaciones de rebaños y también estrategias para organizar grupos de robots orientados al cumplimiento de metas o formaciones. 

%

También buscaremos conocer los patrones que pueden formar nuestros agentes en los videojuegos usando la interacción entre pares que elegimos. Se puede distinguir en modelos de individuos auto-propulsados y con atracción de a pares (pairwise), la emergencia de patrones morfológicos \cite{28}, \cite{29}, \cite{30}. Los patrones de formación emergentes pueden depender de distintos factores: \textit{interacción entre agentes}, \textit{cantidad de agentes}, \textit{propiedades del sistema}, \textit{etc}. Por eso, debemos definir ciertos valores, como la interacción entre agentes.

En videojuegos suele ser requisito que los agentes puedan realizar ciertas formación o patrones, en juegos de estrategia por ejemplo. Pero estas formaciones o patrones se espera en un videojuego que sean más organizadas que la mera agrupación de agentes en un punto. Se espera que las mismas tengan cierta coordinación y organización, característica que ayudará a la imagen de inteligencia que darán los agentes del videojuego. Un ejemplo puede ser el juego \textit{Kingdom Under Fire 2}, donde se desarrollarán grandes batallas y habrá una gran concentración de agentes de distintos tipos. Aquí se espera que los agentes autónomos se organizen dentro de cada grupo al que pertenezcan ya que esto ayudará a dar como resultado un mejor desarrollo de la batalla. Otro ejemplo puede ser \textit{Left 4 Dead 2} donde hay grandes grupos de agentes autónomos que representan zombies que nos atacarán.


%La meta, es lograr el comportamiento como consecuencia de una definición general de la interacción que tendrán dos agentes. En nuestro caso, la definición de la interacción entre agentes se hizo tras estudiar potenciales conocidos de tipo \textit{soft-core} y de tipo \textit{hard-core}.

Para comprender cómo los potenciales afectan el flocking de nuestros agentes debemos pensar en dos agentes cualesquiera separados por una distancia $r_{ij}$. Nuestro rebaño tendrá una distancia de separación deseada $r_{min}$ y uno de los requisitos sobre los mismos, en el videojuego o aplicación que estemos desarrollando, es que sean capaces de evitar colisiones. Esto implica que la fuerza asociada a la componente de repulsión será mayor que la asociada a la componente de atracción cuando $r_{ij} < r_{min}$. Pero también, para mantenerlos agrupados, cuando $r_{ij} > r_{min}$ se quiere que los agentes se atraigan, i.e, la fuerza predominante es la de atracción. Por último, los agentes con $r_{ij} >> r_{min}$ tendrán un grado de interacción que resultará en fuerzás casi nulas, característica que aporta el efecto de localía. Tiene sentido ya que de esta forma el grado en que afectará el agente  $i$ al $j$ dependerá de $r_{ij}$, disminuyendo a medida que $r_{ij}$ aumenta. Esto quiere decir que los vecinos cercanos de un agentes serán los que más afecten su comportamiento.
% será necesario que los agentes sean afectados por una fuerza de repulsión hacia su vecino cuando $r_{ij} < r_{min}$. Luego, la componente asociada a la repulsión del potencial será mayor que la componente asociada a la atracción. 

Dos potenciales ampliamente conocidos para el modelado de la interacción entre moléculas en la física son los potenciales de Morse y Lennard-Jones. Dichos potenciales se comportan de manera similar cuando $r_{ij} > r_{min}$ pero son muy diferentes en el caso $r_{ij} < r_{min}$. La diferencia principal está en la forma en que definen la energía para los agentes cuando este vector \textit{tiende a cero}($\vec{r_{i,j}} \to 0$). Esta diferencia trae aparejada un cambio en el comportamiento de los agentes y por ende en el comportamiento de todo el grupo. Según el comportamiento que tengan en este caso, los potenciales pueden pertenecer a dos tipos: \textit{Soft-core Potencials} o \textit{Hard-core Potencials}.

%\begin{itemize}
%\item \textit{\textbf{Soft-core Potencials}}
%\item \textit{\textbf{Hard-core Potencials}}
%\end{itemize}
% Aquí $r_{ij} \rightarrow 0$ y el potencial de Lennard-Jones al ser de tipo hard-core nos dice que $U \rightarrow \infty$, mientras el potencial de Morse tiene un comportamiento de tipo soft-core, i.e, su potencial tiende a una constante finita. Esta diferencia trae aparejada un cambio en el comportamiento de los agentes y por ende en el comportamiento de todo el grupo.

%incluir imágenes
\begin{figure}[htb]
\centerline{
   \includegraphics[height=3cm, width=8cm]{./img/soft-core-vs-hard-core2new.eps} 
}
\caption{Fig.1 de \cite{sof-vs-hard-core} (a) Representación de dos boids posicionados en $r_i$ y $r_j$ con velocidades respectivas $v_i$ y $v_j$ en direcciones $\theta_i$ y $\theta_j$, con $r_{ij} = r_i - r_j$. (b) Potenciales de Lennard-Jones (línea roja) y Morse (línea punteada).}
\label{mp-lj-comparison}
\end{figure}

Los potenciales del tipo hard-core son potenciales donde \textit{la función que define la energía tiende a infinito cuando la distancia entre agentes tiende a cero}.

\begin{equation}
\vec{r_{i,j}} \to 0 \Longrightarrow U( \vec{x_i} ) \to \infty
\end{equation}
Dentro de este tipo de potenciales es donde pertenece el potencial de Lennard-Jones (L-J), cuya definición genérica es de la siguiente forma

\begin{equation}
U^{L-J}(r) = 4\epsilon \Biggl [\biggl ( \frac{\omega}{r} \biggr)^{12} - \biggl ( \frac{\omega}{r} \biggr)^6 \Biggr]
\end{equation}

donde $r$ es la distancia entre agentes, $\epsilon$ es la profundidad del potencial y $\omega$ es la distancia(finita) a la cual el potencial se define como cero. La ecuación está definida por un término de atracción y un término de repulsión, $r^{-6}$ y $r^{-12}$ respectivamente. 

Para el modelado de un sistema multi-agentes en el que deseamos lograr un comportamiento de rebaño, la ecuación que define el potencial para un agente suele definirse como a continuación

\begin{equation}
U^{L-J}_i(r) = \sum_{i\neq j} \epsilon \Biggl [\biggl ( \frac{r_{min}}{r_{ij}} \biggr)^{12} - \biggl ( \frac{r_{min}}{r_{ij}} \biggr)^6 \Biggr]
\end{equation}

donde $U^{L-J}_i$ es el potencial entre el agente $i$ y el resto de los agentes del sistema, $\epsilon$ y $r_{min}$ dan la forma del potencial y $r_{ij}$ es el vector distancia. El mínimo de este potencial ocurre cuando $r = r_{min}$, que suele interpretarse como la separación deseada entre dos agentes. 

%Por otro lado, tenemos los potenciales del tipo \textit{soft-core} son potenciales donde la función que define la energía no diverge cuando la separación entre agentes tiende a cero, $r_{ij} \to 0$. El potencial de Morse es de este tipo. La definición generalizada que usamos es la siguiente
Por otro lado, tenemos los potenciales del tipo \textit{soft-core}, donde la energía no diverge cuando la separación entre agentes tiende a cero, $r_{ij} \to 0$. El potencial de Morse es de este tipo y la definición generalizada que usamos es la siguiente

\begin{equation}
U^M(\vec{x_i}) = \sum_{i\neq j} \biggl [C_{r}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{r}}} - C_{a}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{a}} } \biggr]                                                                                                                                               
\end{equation}

donde $U^M(\vec{x_i})$ es el potencial entre el agente $i$ y el restro de los agentes del sistema.

Explicaremos más en detalle este potencial en la sección siguiente, ya que fue el potencial elegido para el modelado continuo. Se eligió este potencial principalmente por ser de tipo soft-core.La parametrización de dicho potencial, junto a características del sistema como posiciones iniciales de los agentes, sus velocidades y cantidad de agentes, trea aparejada la emergencia de patrones. Estos patrones pueden cumplir ciertos invariantes como la formación de grupos, anillos, sentido de rotación, etc. Por lo tanto se pueden identificar distintos tipos de patrones. 


\subsubsection{• Potencial de Morse}
\label{sectionMorse}
El potencial de Morse es una elección común para el modelado de la interacción de agentes en sistemas multi-agente, como en \cite{vehicleflocking}, donde se lo usa para lograr un control cooperativo de vehículos autónomos. Este potencial, al igual que el de Lennard-Jones, está compuesto de dos términos: \textit{atracción} y \textit{repulsión}. La ecuación que define el potencial en su versión generalizada es la siguiente (\ref{morse}).

\begin{equation}
\label{morse}
U(\vec{x_i}) = C_{r}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{r}}} - C_{a}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{a}} }                                                                                                                                               
\end{equation}

donde $C_a$ y $C_r$ representan respectivamente las amplitudes de atracción y repulsión, y $l_a$ y $l_r$ representas respectivamente sus rangos de atracción y repulsión.

Como se puede notar, el potencial de una partícula $x_i$ se calcula tomando como referencia alguna otra partícula $x_j$ del sistema, y el valor final $U(\vec{x_i})$ es la suma de todos los potenciales calculados desde la partícula $x_i$ hacia cada una del resto de las partículas del sistema. Cabe destacar que se podría elegir otro potencial de los denominados \textit{de a pares(pairwise)} y ver que incidencias tiene en el sistema, la predicción de formas emergentes y estabilidad del sistema.

En nuestro caso de estudio vamos a suponer un sistema de \textit{N} agentes. Cada uno de estos agentes será afectado por cierta atracción y repulsión proveniente del resto de los \textit{N-1} agentes del sistema. Dicha atracción y repulsión será calculada usando la ecuación (\ref{morse}), dejando el potencial de cada agente determinado por el siguiente cálculo:

\begin{equation}
\label{potencial-individual}
U(\vec{x_i}) = \sum_{i\neq j} \biggl [C_{r}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{r}}} - C_{a}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{a}} } \biggr]                                                                                                                                               
\end{equation}

donde $x_i$ es el agente \textit{i-ésimo} del sistema.

Lo que se intenta es tratar de comprobar que se cumplan las predicciones de formaciones y de estabilización en los sistemas multi-agente que se muestran en \cite{self-propelled-particle}. Para esto debemos mostrar las ecuaciones de movimiento que rigen para las N partículas de nuestro sistema

\begin{equation}
 \vec{v_{i}} = \frac{\delta x_{i}}{\delta t}
\end{equation}

\begin{equation}
\label{fuerza}
m \frac{ \delta \vec{v_{i}} }{\delta t} = (\alpha - \beta |\vec{v_{i}}|^{2} ) \vec{v_{i}} - \vec{\nabla}_{i} (\vec{x_{i}}) 
\end{equation}

donde $\alpha, \beta > 0$ son valores efectivos de propulsión y fuerza de fricción. También se decidió por una cuestión de generalización y simplicidad hacer \textit{m=1} para todos los agentes del sistema.

Para una fuerza independiente de la velocidad necesitaríamos $\alpha, \beta = 0$, lo que hace que las ecuaciones (\ref{potencial-individual})-(\ref{fuerza}) describan un \textit{sistema Hamiltoneano} con conservación de energía. También esperamos que se cumplan las condiciones de estabilidad para sistemas Hamiltoneanos. Dado un conjunto de \textit{N} partículas interactuando entre si, la energía potencial total del sistema \textit{U} se dice H estable si existe una constante $B \geq 0$ tal que $U \geq -NB$. Esto nos asegura que el conjunto de partículas no colapse cuando $N\rightarrow \infty$.

Los sistemas \textit{no H estables} se dicen \textit{catastróficos}, en cuyo caso a medida que N crece las partículas del sistema convergen agrupándose todas alrededor de un punto. Esto se desprende de que la energía total $U < 0$, por lo que la componente de atracción del potencial de Morse es la que predomina, haciendo que las partículas se atraigan entre sí, concentrándose en un punto.

Las formas y patrones que emergen del sistema se divide en regiones que son determinadas por las amplitudes relativas $C = \frac{C_r}{C_a}$ y $l = \frac{l_r}{l_a}$. Como vemos en la Figura \ref{regiones} las regiones catastróficas y H-estables están separadas por la curva $Cl^2 = 1$. 

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm]{img/regiones-morse.eps}
}
\caption{Regiones Potencial de Morse. Reproducción de la figura NR. 1 de \cite{self-propelled-particle}}
\label{regiones}
\end{figure}


\newpage
\subsubsection{• Algoritmo}
Para lograr la simulación partiremos entonces de un sistema formado por $N$ agentes, los cuales sean idénticos entre sí, tengan una noción de espacio y puedan moverse en él. Se ubicarán en un entorno, que en nuestro caso será de dos dimensiones (2D) y comenzarán con posiciones y velocidades iniciales aleatorias. Se dispondrá de un entorno no acotado, i.e, los agentes se pueden mover libremente por el mismo. Característica que, si bien aumenta la complejidad de la formación de grupo ya que los agentes pueden alejarce al punto de que las fuerzas de atracción sean demasiado pequeñas, nos ayuda a que las simulaciones sean más parecidas al comportamiento natural, o capturen mejor lo que sucede en la realidad. 

Comenzemos entonces por dar una mirada global de cómo será el algoritmo que seguiremos para lograr la simulación:
\begin{enumerate}
\item Setear las posiciones de los agentes, de forma \textit{aleatoria}.
\item Setear las velocidades iniciales de los agentes, de forma \textit{aleatoria}.
\item Actualizar las posiciones de los agentes. Teniendo en cuenta el \textit{potencial de Morse}.
\end{enumerate}

Las posiciones iniciales se dispusieron de forma \textit{aleatoria} dentro de un \textit{círculo} con \textit{radio} igual a $R = N * l_a$, donde $ N $ en nuestro caso es 3 pero puede ser definido por el usuario según su deseo o necesidad y $l_a$ es el \textit{rango de atracción} del potencial de Morse. El centro del \textit{círculo} también se puede customizar según sea necesario. Recordar que una posición inicial aleatoria con un rango de valores muy grande ($>> l_a$) puede disminuir mucho la interacción inicial, afectando el patrón final. Fue por esta razón que se acotó la zona donde se eligen posiciones iniciales.

%Aquí hay que tener en cuenta que como el entorno donde se sitúan los agentes no tiene límites, una \textit{posición inicial random} para los agentes donde el rango de valores sea muy grande ($>> l_a$) puede alejar demasiado a los agentes haciendo que éstos practicamente no sientan la interacción del resto de los agentes del sistema.

También es importante acotar el rango de generación de velocidades iniciales, ya que estas pueden ser demasiado altas. En este caso, los agentes seguirán su movimiento en la dirección del vector velocidad inicial, sin poder organizarse en grupo pues la interacción con el resto de los agentes afectará muy poco su velocidad, aunque la ecuación \eqref{fuerza} nos indique que el modelo sea independiente de la velocidad. Para poder setear un rango para las velocidades iniciales se definió para cada simulación una velocidad máxima haciendo uso del \textit{máximo del potencial de Morse (max\_potencial)} para los parámetros de la simulación que se desea correr.

\begin{mylisting}
\begin{verbatim}
max_potencial = C_r - C_a

# Asigno una energia cinetica maxima al sistema
if max_potencial < 0:
        MAX_KINETIC = 0.5 * -potencial
    else:
        MAX_KINETIC = 0.9 * potencial

# Defino la velocidad maxima de un agente
MAX_VEL = math.sqrt(2*MAX_KINETIC)
\end{verbatim}
\end{mylisting}

Luego podemos usar $MAX\_VEL$ como tope de la velocidad inicial para generar una velocidad aleatoria $v_i$ tal que $0 \leq v_i \leq MAX\_VEL$. Esta elección de velocidad máxima es una y se puede cambiar para otras simulaciones.

Por último, para actualizar las posiciones necesitamos un bucle en el cual cada agente calcule su gradiente del potencial de Morse y lo use para obtener la fuerza que definirá su comportamiento. Esto es, actualizar sus posiciones según las ecuaciones de movimiento empleadas y la fuerza calculada en base a la ecuación \eqref{fuerza}.

%Para esto se decidió usar el algoritmo de Verlet Velocity\cite{verlet_velocity}, un método numérico de integración de las ecuaciones de movimiento de Newton, muy popular en las \textit{simulaciones de dinámica de moléculas}.

\subsubsection{• Verlet Velocity}
Para actualizar las posiciones se decidió usar el método Verlet, y de sus algoritmos se aplicó el \textit{Velocity Verlet}. Es un método numérico de integración de las ecuaciones de movimiento de Newton, muy popular en las \textit{simulaciones de dinámica de moléculas}.

Aquí cada agente puede ser identificado por su vector posición $\vec{r}(x_i) = (x_i,y_i)$. Pero vimos que su posición y velocidad dependerán de la fuerza que se ejerce sobre los mismos en cada instante, proveniente de interacciones con el medio y el resto de los agentes, en las que incide el potencial de Morse. Por lo tanto las ecuaciones asociadas a los agentes y su distribución en el entorno serán:

% estos agentes, con el tiempo, cambian su posición debido a interacciones con el medio y el resto de los agentes. Luego, cada uno de los $N$ agentes tienen una posición y una velocidad en función del tiempo, que será consecuencia de la fuerza que se ejerce en cada instante de tiempo sobre cada agente proveniente de la interacción con el resto de los agentes, en la que incide el potencial de Morse. 

\begin{equation}
\begin{split}
\begin{aligned}
	 \vec{r}(x_i)(t)\\
	 \vec{v}(x_i)(t)\\
	 \vec{f}(x_i)(t)\\
      \end{aligned}
\Bigg\rbrace \forall i :  0\leq i \leq N
\end{split}\end{equation}

%Luego, fue necesario integrar las ya conocidas ecuaciones de movimiento de Newton para poder calcular las trayectorias de los agentes. Para esto se decidió usar el método de integración 

Lo que hace este algoritmo es actualizar las posiciones, velocidades y aceleraciones para intervalos $\Delta t$ usando los valores en tiempo $t$ de la siguiente manera

\begin{enumerate}
\item Actualizar $\vec{r}(x_i)(t+ \Delta t) = \vec{r}(x_i)(t) + \vec{v}(x_i)(t)*\Delta t+ \frac{\vec{a}(x_i)(t)(\Delta t)^^2}{2}$
\item Actualizar $\vec{v}(x_i)( t+ \frac{\Delta t}{2}) = \vec{v}(x_i)(t) + \frac{\vec{a}(x_i)(t)*\Delta t}{2}$
\item Actualizar $\vec{a}(x_i)(t+ \Delta t)$ usando el potencial elegido.
\item Actualizar $\vec{v}(x_i)(t+\Delta t) = \vec{v}(x_i)(t+ \frac{\Delta t}{2}) + \frac{a(x_i)(t+\Delta t )*\Delta t}{2}$
\end{enumerate}

donde $a(x_i)(t)$ se calcula de la siguiente manera,
\begin{equation}
\begin{split}
\begin{aligned}
a(x_i)(t) &= f(x_i)(t)/m\\
m &= 1 
\end{aligned}
\Bigg \rbrace \Longrightarrow a(x_i)(t) = f(x_i)(t)
\end{split}
\end{equation}

Ya habiendo definido la interacción entre los agente, de que manera afectará dicha interacción en su movimiento dentro del entorno no acotado y habiendo definido también la forma en que se actualizarán las posiciones y velocidades de los agentes, nos encontramos en situación de implementar el modelo hasta ahora mostrado.

\newpage
\subsubsection{• Implementación}

El modelo continuo que deseamos implemnentar cuenta basicamente de dos elementos:
\begin{itemize}
\item Entorno
\item Agentes
\end{itemize}

El entorno, será representado por un espacio 2D no acotado donde los agentes podrán moverse libremente. Los agentes, serán un grupo de individuos o \textit{boids} de iguales características que interactuarán entre si. La implementación se hizo usando el lenguaje Python\cite{python}, el cual es orientado a objetos. Por lo tanto, para representar a los agentes se decidió crear una clase \textit{Agente()} la cual se implementó como un Sprite de Pygame\cite{pygame} de la siguiente manera:


\begin{mylisting}
\begin{verbatim}
class Agente(pygame.sprite.Sprite):
    
    def __init__ (self, img=None):
        global NUMERO,GLOBAL_VAR
        # Inicializo posicion, velocidad, aceleracion y fuerza en (0,0)
        self.pos = (0,0)
        self.vel = [0,0]
        self.acel = [0,0]
        self.fuerza = [0,0]
        # Cargo numero de identificacion del agente
        self.id = NUMERO
        # Genero proximo numero de identificacion
        NUMERO += 1
        # Inicializo la masa del agente igual a 1
        self.masa = 1.0
        
        if GLOBAL_VAR['GRAFICO']:
            # Inicializo Sprite
            pygame.sprite.Sprite.__init__ (self) 
            
            # Cargo imagen y rectangulo de imagen
            self.image, self.rect = load_image(name)
            
            # Recupero la pantalla
            screen = pygame.display.get_surface()
            
            # Guardo area de la pantalla
            self.area = screen.get_rect()
            
            # Defino una escala para el renderizado
            self.escala = 25
            
            # Situo al agente en la posicion inicial
            self.rect.centerx, self.rect.centery = self.pos[0], self.pos[1]

\end{verbatim}
\end{mylisting}

Los agentes de nuestro prototipo serán todas instancias de la clase Agente, lo que nos asegura que sean idénticos y tengan los mismos métodos definido. Si fuera necesario tener otro grupo distintos de agentes se podría o bien definir completamente una nueva clase de agentes, o bien contar con una definición genérica de clase heredar de esta, definiendo los métodos necesarios.

Uno de los métodos más importantes de la clase será el que calcula la interacción con el resto de los agentes. En nuestro modelo, será el método encargado en calcular la fuerza, ecuación \eqref{fuerza}, que dependerá del potencial de Morse. Pero para esto, lo que necesitamos calcular es el \textit{gradiente} de este potencial. Esto se debe calcular para cada agente o boid del sistema, por lo que se implementó un método dentro de esta clase Agente que lo calcule. Este método se llamó \textit{gradiente\_potencial\_morse()} y se implementó de la siguiente manera

\begin{mylisting}
\begin{verbatim}
def gradiente_potencial_morse(self):
        global GLOBAL_VAR, agentes
        # Cargo parametros del potencial
        C_a = GLOBAL_VAR['C_a']
        l_a =GLOBAL_VAR['l_a']
        C_r =GLOBAL_VAR['C_r']
        l_r =GLOBAL_VAR['l_r']
        alpha =GLOBAL_VAR['alpha']
        beta =GLOBAL_VAR['beta']
        
        # Seteo a 0 las variables donde se guardara el valor del gradiente
        gradiente_coordenada_x = 0
        gradiente_coordenada_y = 0
        
        # Calculo factor repulsion y atraccion
        f_r = C_r/l_r
        f_a = C_a/l_a
        
        # Calculo el gradiente del potencial para todo agente distinto a 
        # mi mismo
        for agent in agentes:
            if agent.id == self.id:
                # Si soy yo continuo
                continue
            
            # Guardo distancia por coordenadas desde mi posicion al agente
            dist_x = self.pos[0] - agent.pos[0]
            dist_y = self.pos[1] - agent.pos[1]
            
            # Calculo el modulo de la distancia
            mod_r = math.sqrt(dist_x**2+dist_y**2)
            
            if (mod_r) < 1e-3:
                # Si la distancia es muy chica entonces no lo tomo en cuenta
                continue
            
            # Calculo los factores del potencial
            e_r = math.pow(math.e, -(mod_r)/l_r)
            e_a = math.pow(math.e, -(mod_r)/l_a)
            
            # Calculo la repelencia y atraccion
            rep = f_r*e_r
            atrac = f_a*e_a
            
            # Sumo a las coordenadas del gradiente lo correspondiente al 
            # agente que estoy teniendo en cuenta
            gradiente_coordenada_x += (-dist_x/mod_r)*( rep - atrac)
            gradiente_coordenada_y += (-dist_y/mod_r)*( rep - atrac)
        
        # Devuelvo valor del gradiente por coordenadas
        return [gradiente_coordenada_x,gradiente_coordenada_y ]
\end{verbatim}
\end{mylisting}

Este método será usado para calcular la fuerza sobre el agente. El método que lo usará calculará la aceleración del agente teniendo en cuenta la ecuación \eqref{fuerza} y se implementó de la siguiente manera:

\begin{mylisting}
\begin{verbatim}
def update_aceleration(self):
        global GLOBAL_VAR
        
        # Cargo constantes de la ecuacion
        alpha =GLOBAL_VAR['alpha']
        beta =GLOBAL_VAR['beta']
        
        # Calculo el gradiente
        gradiente = self.gradiente_potencial_morse()
        
        # Calculo modulo de velocidad del agente
        vel = math.sqrt(self.speed[0]**2 + self.speed[1]**2)
        
        # Calculo parte de lo relacionado a la velocidad
        factor_vel = (alpha - beta*(vel**2))
        
        # Calculo la fuerza por coordenadas
        self.fuerza[0] = factor_vel*self.speed[0] - gradiente[0]
        self.fuerza[1] = factor_vel*self.speed[1] - gradiente[1]

        # Devuelvo la aceleracion por coordenadas
        return [self.fuerza[0]/self.masa, self.fuerza[1]/self.masa]

\end{verbatim}
\end{mylisting}

Cabe destacar que de ser necesario utilizar el prototipo aquí planteado pero con otro potencial, solo hace falta modificar el método que calcule la aceleración. Para que deje de llamar al método que calcula el gradiente de Morse y llame a un nuevo método que será el encargado de definir la nueva interacción y en base a estos valores calcule la nueva aceleración. Esta es una caracteristica que se cree positiva para realizar cambios futuros. En la sección \ref{sectionMorse} se mostraron ilustraciones sobre simulaciones hechas con la implementación aquí planteada.


\newpage
\subsection{• Sensores}\label{subsection-sensores}
Ya hablamos de la organización y formación de patrones de en sistemas multi-agente cuyos algoritmos son \textit{continuos} o \textit{discretos} y algo que tienen en común ambos es que de alguna forma interpretan el medio y existe la noción de distancia, que nos permite calcular el vector $r_{ij}$. Datos como estos son obtenidos vía sensores y los agentes de los sistemas estudiados los poseen. Se estudiaron e implementaron sensores de distintos tipos: \textit{sensores basados en visibilidad geométrica y sensores basados en propagación en el medio}. Dentro del primer grupo de sensores se implementaron \textit{sensores de distancia y sensores de visibilidad}. Mientras que dentro del segundo grupo de sensores se implementó un \textit{sensor de presión}. Para que entendamos mejor el funcionamiento y la necesidad de los sensores veamos la siguiente Figura \ref{agent-structure}.
%Estos sensores son los que se encargan de captar información del medio, que luego será procesada, junto con información interna del agente, por los algoritmos de rebaño para producir alguna acción que tomará el agente.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm, width=5cm]{img/AgentStructure.eps} 
}
\caption{Diagrama de un agente, su interacción con el medio(vía sensores) y su actuación basada en lo censado y su estado interno}
\label{agent-structure}
\end{figure}


En la Figura \ref{agent-structure} se muestra un agente (círculo), que tiene un vector de estados internos \textit{(is,internal states)}. Estos estados internos en un tiempo $t+\Delta t$ dependen tanto de sus valores en $t$ como de lo censado del \textit{sistema} en un tiempo $t$. Cada agente posee una cantidad $n$ de sensores \textit{(s)} que producen valores escalares en un tiempo dado, siendo $s_i(t)$ lo censado en el tiempo $t$ por el sensor $i$.

Los agentes tienen una forma de reaccionar ante ciertos estados, para esto poseen actuadores o efectuadores \textit{(a, actuators)} estos actuadores producen valores escalares, siendo $a_i(t)$ el valores del actuador $i$ para el tiempo $t$. El valor del actuador, se interpreta como una medida de alguna acción que puede tomar el agente. Por ejmplo, supongamos un videojuego donde el agente emite siempre un sonido para que el resto de sus pares lo puedan oir y así agruparse, entonces si en un tiempo $t$ emitirá un sonido $a_i(t)$(donde el actuador $a_i$ es el que emite el sonido) y este sonido puede aumentar o disminuir según tenga pocos o muchos vecinos cerca. De esta forma, cuanto más solo se encuentre mayor será $a_i(t)$, para poder cubrir un area más grande donde lo escuchen otros agentes. También podemos pensar que el agente es un automovil en una carrera y que $a_i$ es el actuador relacionado a la aceleración. Luego, dependiendo de las distancias al resto de los automoviles y de la ruta, $a_i$ podrá aumentar o disminuir, haciendo que la aceleración del automovil aumente o diminuya respectivamente. Desde el punto de vista del agente, $s$ son los inputs y $a$ son los outputs. Por lo que podemos pensar en una función $f$ (pueden ser mas de una función) que toma los valores de los sensores y los valores de los estados internos y devolviendo valores de los actuadores y valores de los estados internos. Adicionalmente los estados internos pueden tener una dinámica propia. Lo que se llama \textit{reglas}(o rules) en un agente son las funciones $f$. Luego, la aplicación de una regla podría definirse como

\begin{equation}
f(s, is) = [a, is']
\end{equation}

donde $is'$ es el nuevo estado interno de nuestro agente. Un ejemplo de una regla de separación, donde $s$ es el sensor que devuelve la distancia al vecino más cercano. Veamos el caso de $s \geq minSep $.

\begin{equation}
f_{sep}(s, is) = [continue, is]
\end{equation}
aquí la distancia al vecino más cercano es mayor que la separación mínima que se desea mantener ($s \geq minSep $) por lo tanto la acción es continuar($continue$), o hacer nada, y el estado interno quede igual.

Ahora veamos la otra opción, donde $s \< \leq min\_sep$,
\begin{equation}
f_{sep}(s, is) = [move\_away, is]
\end{equation}
 
aquí la acción que se toma es la de alejarse del vecino ($move\_away$).


\subsubsection{• Distancia}
El sensor de distancia fue necesario en todos los algoritmos de rebaño implementados. En los algoritmos de tipo \textit{continuo} es clara la necesidad pues el cálculo del \textit{potencial de Morse} se basa en el vector distancia a cada agente del sistema. En los algoritmos de tipo \textit{discreto}, como vimos antes, es necesario calcular el conjunto de vecinos para cada agente. También era necesario calcular el vecino más cercano y poder saber la distancia a éste era vital para saber si se debía aplicar de la regla de \textit{separación} o \textit{alineación y cohesión}.

Para el cálculo de la distancia nos basamos en que todos los sistemas multi-agente que se estudiaron fueron en dos dimensiones. Por lo que todo agente tiene su posición identificada en base a dos coordenadas (x, y), como así también su velocidad y aceleración.


\begin{figure}[h!t]
\centerline{
   \includegraphics[height=3cm, width=4cm]{img/vector_distancia.eps} 
}
\caption{Vector distancia entre agentes $i$ y $j$.}
\label{vector-distancia}
\end{figure}



\subsubsection{• Visión}
Otro de los sensores que se implementaron fue el de visión. Lo que se intenta hacer con esto es acotar la funciones antes aplicadas sobre los agentes. Hasta ahora la actuación de un agente la podíamos pensar como una función ($\chi$) que depende de los $N$ integrantes más el sistema ($E$).

\begin{equation}
[a_i, is_i] = \chi(x_1, x_2,..., x_{i-1},..., x_N) 
\end{equation}

donde $\chi$ es la función que define la actuación del agente $i$ $\forall i \in \{1, ..., N\}$.

Ahora, si agregamos un sensor de visión, llamémoslo $\psi $, tal que:
\begin{equation}
\psi(i)=\{\ j \in \{1, ..., N\}:\ el\ agente\ j\ esta\ en\ el\ rango\ de\ vision\ de\ i\}
\end{equation}

y restringimos $\psi$ para que su resultado no sea siempre $\{1, ..., N\}$ entonces si aplicamos $\chi$ de la siguiente forma:
\begin{equation}
[a_i, is_i] = \chi \odot \psi(i)
\end{equation}

lo que estaremos haciendo es acotar el alcance de la función $\chi$.

Para lograr lo requerido se decidió utilizar una adaptación en python de la librería \textit{VisiLibity} \cite{visiLibity}, escrita originalmente en C++. La adaptación hecha para usarla en nuestro trabajo y sus modificaciones fueron enviadas al autor y publicadas por este en la página oficial \footnote{\url{http://visilibity.org}}.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=4cm, width=4cm]{img/area_vision.eps} 
}
\caption{Rango de visión de un agente.}
\label{vision-agente}
\end{figure}

\subsubsection{• Algoritmo VisiLibity}
El algoritmo \textit{Visilibity}, necesita primero que se defina un ambiente, esto se hace a través de la definieción de un polígono. Este ambiente es un area cerrada que contendrá a nuestro agente y generalmente se la elige de forma que contenga el rango de visión que se desea definir. Para simulaciones en tiempo real, no es necesario demarcar un ambiente cuya superficie es varias veces mayor al rango de visión ya que esto debendrá en una aumento de cálculos sobre los polígonos de visión, afectando la performance de simulación. %Situación que no sucede si lo que se quiere es hacer una simulación en modo off-line. Pero esta no es una situación que vemos con frecuencia en videojuegos.

En la librería que implementa el sensor, al agente que va a aplicar el algoritmo de visión se lo conoce como \textit{observador}. Este será quien utilize el sensor dentro de un ambiente para identificar a los agentes que se encuentren en su rango de visión. Pero esta no es la única utilidad que se le puede dar al sensor, ya que el mismo también es útil para problemas de \textit{pathfinding}(búsqueda de caminos). Para hacer esto se debe definir un punto en nuestro ambiente que será similar al observador, solamente que este será el objetivo(\textit{target}) de nuestro observador, el algoritmo nos dirá si el objetivo está en nuestro polígono de visión y cual es la ruta más corta al mismo, característica útil en el desarrollo de videojuegos.

Por último, el algoritmo también nos permite añadir obstáculos(\textit{holes}) para el observador, cuya figura es definida usando polígonos, lo que otorga una gran libertad al desarrollador al momento de codificar o diseñar un escenario. Estos obstáculos pueden ser útiles por ejemplo para diseñar calles, laberintos o habitaciones y otros tipos de escenarios. El observador no podrá ver a través de los obstáculos que se encuentren en su rango de visión, por lo que éstos afectarán el polígono de visión efectiva del agentes disminuyendo su área. Entonces, un punto que se encuentre frente al observador, dentro de su rango de visón pero con un obstáculo delante de él, aunque sea cierto que pertenece al rango de visón, no pernecerá al área que defina su polígono de visón, quedando fuera del alcance del observador.

Para nuestros casos de uso, los observadores y objetivos se definieron ambos con puntos, donde en cada intervalo de tiempo se recorría a los agentes aplicando el sensor de visión, con una rango y figura definido, teniendo como objetivos al resto de los agentes. De esta manera obtenemos el conjunto de agentes vecinos.

A los agentes se los puede pensar también como holes, esto es, que obstruyan la visibilidad del observador, o bien se pueden implementar como puntos en el plano, cuya área no será suficiente para obstruir la visión. Aquí se han implementado soluciones del último tipo, ya que se intentó bajar los tiempos de simulación. Pero para implementar una solución del primer tipo solo basta definir el polígono que represente al agente. En la Figura \ref{ejemplo-visilibity} podremos ver un ejemplo del uso de la librería.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=10cm, width=12cm]{img/visilibity-test.eps} 
}
\caption{Test de librería \textit{VisiLibity}. Los polígonos rojos son obstáculos para la visión(holes), el punto azul en el centro es el observador, el rojo es un punto fuera del polígono de visión del observador mientras que el punto verde se encuentra dentro del polígono de visión del observador.}
\label{ejemplo-visilibity}
\end{figure}

Una vez implementado el sensor de visibilidad y probado su correcto funcionamiento, se decidió integrarlo al modelo continuo basado en el potencial de Morse. 

\subsubsection{• Integración}
Hasta aquí el modelo basado en potenciales se aplicaba sobre todos los agentes del nuestro sistema. Fue por eso que se integró un sensor de visión. Si pensamos al algoritmo de flocking basado en Morse como una función cuyo dominio es el universo de agentes, entonces lo que buscamos hacer con el sensor es que su dominio se acote a un subconjunto del dominio original. En particular puede suceder que el subconjunto sea igual al conjunto dominio original, situación que puede desprenderse de un agrupamiento de los agentes y un radio y ángulo de visión lo suficientemente amplios para abarcar a todos los agentes. 

Trataremos de ver si algunos de los patrones conseguidos anteriormente se mantienen o se pierden con esta limitación. Así como el modo en que afecta al sistema multi-agentes regirse, por un lado con el potencial de \textit{Morse} y por otro lado con el sensor de visión. Para hacer esto lo que se hizo fue calcular el potencial de \textit{Morse} pero para todos los agentes que se encuentren dentro del cono de visión definido previamente en el archivo de configuraciones.




\subsubsection{• Presión}

Por último se implementó un sensor que se base en la propagación en el medio. Este tipo de sensores (sensores de presión, calor, sonido, etc.) son muy útiles tanto en videojuegos como en simulaciones formales que busquen investigar el comportamiento o evolución de una situación de la naturaleza en un entorno bien definido. Sabemos que intentar simular todas las variables de la vida real es demasiado complejo, pero haciendo alguna simplificación del entorno que nos interese, y enfocándonos en un conjunto más reducido de las propiedades de un entorno real, queremos ser capaces de estudiarlo o simularlo de la manera más real posible y usando métodos computacionales conocidos y de baja complejidad para el desarrollador.

Lo que se pretende con este sensor es capturar una propiedad que se propaga en el entorno y evoluciona con el mismo. Para esto debió replantearse el entorno al que pertenecen los agentes, debido a que por su simplicidad no permitía implementar una manera optimizada de propagación. Lo que se estudió e implementó especificamente fue la propagación de ondas de presión en un medio. Los agentes pasarán entonces a formar parte de un entorno más real, ganando expresividad. Permitiremos que el desarrollador pueda ahora medir estados del sistema y ajustar su evolución según lo crea necesario. También será posible que los agentes interactúen con el medio, cambiando su estado según el juego lo requiera o las mismas características del agente.
%\newpage
%\subsubsection{• Patrones - Regiones}
\newpage

\subsection{• Propagación en Medio Material}\label{subsection-propagacion}

Para propagar la presión se decidió simular el medio usando un Autómata Celular(CA). Los CA son una excelente herramienta para las simulaciones, están fuertemente ligados a la inteligencia artificial por la flexibilidad y simplicidad para simular sistemas complejos y de muchos estados.

\subsubsection{• CA}\label{subsubseccion-ca}
Un \textit{Autómata Celular} es una grilla o matriz de celdas o células, que se rige en base a reglas generales que se aplican a todas las celdas. Gran parte de su popularidad se basa en que con un conjunto chico de reglas se pueden simular sistemas complejos. Los \textit{CA} también muestran el concepto de \textit{emergencia}, i.e, como a partir de interacciones locales emergen patrones en el sistema global.

El estado actual, digamos un tiempo $(t)$, de un CA se define en base al estado que tengan las celdas que lo componen. Mientras que el estado en el próximo paso de tiempo $(t+1)$ depende del estado en $t$ y la aplicación de las reglas para cada celda. Estas celdas definen su estado en base a un conjunto de valores que pueden tomar, previamente definido. Sea $\lbrace \eta_1, \eta_2, ....,\eta_n \rbrace$ el conjunto de estados que puede tomar cada celda del CA. 

Las reglas se aplican de forma síncrona a todas las celdas que componen el CA generando el nuevo estado del CA. %El nuevo valor de las celdas depende de la aplicación de las reglas y el estado de los vecinos de la celda en ese instante. Esto es:

\begin{equation}
\begin{split}
\begin{aligned}
\varepsilon_0 &= Estado\ inicial; \\\
\varepsilon_1 &= \xi(\varepsilon_0);\\
\varepsilon_2 &= \xi(\varepsilon_1);\\
\varepsilon_3 &= \xi(\varepsilon_2);\\
&...\\
\varepsilon_{n+1} &= \xi(\varepsilon_n)
\end{aligned}
\end{split}
\end{equation}

donde $\varepsilon_i$ es el estado $i$ y $\xi$ es la función que aplica las reglas definidas a todo CA, haciendo evolucionar su estado.

%La aplicación de la función $\xi$ es el resultado de aplicar de forma síncrona las reglas a cada celda del CA. Esta aplicación de reglas a cada celda depende del estado de la misma en ese instante de tiempo y el de sus \textit{vecinos}. 

Para la aplicación de reglas, los CA usan el concepto de \textit{vecindad(neighbourhood)}. Analizamos dos tipos de vecindades para CA de dos dimensiones, la \textit{vecindad de Von Neumann} y la \textit{vecindad de Moore}. La vecindad de Von Neumann consta de los vecinos al norte, sur, este y oeste de cada celda, dando un total de cuatro vecinos por celda. Mientras que la vecindad de Moore consta de ocho vecinos, los cuatro de Von Neumann más los cuatro diagonales. Definido más formalmente esto queda como a continuación.

\begin{equation}
\Theta(\varphi_{i,j}) = \lbrace \varphi_{i-1,j}, \varphi_{i+1,j}, \varphi_{i,j-1}, \varphi_{i,j+1} \rbrace
\end{equation}

\begin{equation}
\begin{split}
\begin{aligned}
\Gamma(\varphi_{i,j}) = \lbrace &\varphi_{i-1,j-1}, \varphi_{i-1,j}, \varphi_{i-1,j+1}, \varphi_{i,j-1},\\
&\varphi_{i,j+1}, \varphi_{i+1,j-1}, \varphi_{i+,j}, \varphi_{i+1,j+1} \rbrace
\end{aligned}
\end{split}
\end{equation}

siendo $\Theta$ la función que define la vecindad de \textit{Von Neumann}, $\Gamma$ la función que define la vecindad de \textit{Moore} y con $\varphi_{i,j}$ que define unívocamente una celda en la grilla del CA. Podemos ver una ilustración en la Figura \ref{vecindades}.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=4cm, width=6.5cm]{img/vecindades-ca.eps} 
}
\caption{Vecindades de CA. Figure 1 de \cite{ca-spreadsheet} }
\label{vecindades}
\end{figure}


El siguiente estado de una celda, entonces, lo podemos definir más claramente con la ecuación \eqref{next-state}:

\begin{equation}
\label{next-state}
\xi(\varphi_{i,j},t+1) \in \lbrace \eta_1, \eta_2, ....,\eta_n \rbrace
\end{equation}

donde $\xi$ es la función que refleja las reglas del autómata, dando como resultado el estado o valor que tomará la celda $\varphi_{i,j}$ en el tiempo $t+1$. Cabe destacar que no es necesario que los estados de cada celda sean un conjunto finito, puede darse el caso en que su conjunto de valores no sea finito.

Por lo tanto, podemos definir un autómata celular como un sistema que se compone de: \textit{un estado inicial, es espacio discreto, un tiempo discreto, un conjunto de estados posibles para cada celda, un conjunto de reglas y, si la matriz no es infinita, condiciones de frontera (que definen reglas a aplicar para las celdas que se encuentran en las fronteras de la matriz)}

\subsubsection{• Conways's Game of Life}

Como apéndice extra se implementó el \textit{Juego de la vida (Game of Life)}, probablemente el CA más popular que existe. Es un autómata celular creado por el matemático John Conways. Podemos leer información general del \textit{Juego de la Vida} en \cite{paul-collahan-math}. 

En este CA el conjunto de valores o estados posibles que puede tomar cada celda es un conjunto binario: $\lbrace viva,\ muerta\rbrace$, o $\lbrace 1,\ 0 \rbrace$, o $\lbrace negro,\ blanco \rbrace$. Las reglas que rigen el comportamiento del CA son:

\begin{enumerate}
\item Una celda \textit{muerta} y con \textit{exactamente} 3 vecinos \textit{vivos}, \textit{vive} en la siguiente generación (\textit{reproducción}).
\item Una celda \textit{viva} con 2 o 3 vecinos \textit{vivos} permanece viva la siguiente generación (\textit{persistencia}).
\item Una celda \textit{viva} con 4 o más vecinos \textit{vivos} \textit{muere} la próxima generación (\textit{superpoblación}).
\item Una celda \textit{viva} con menos de 2 vecinos \textit{vivos}, \textit{muere} en la próxima generación (\textit{aislamiento})
\end{enumerate}


El \textit{Juego de la Vida} de Conway ha sido ampliamente estudiado para tratar de entender \textit{complejidades emergentes} y \textit{sistemas auto-organizados}, tal como nos intereza estudiar en este trabajo. Este autómata nos muestra la emergencia de patrones o comportamientos muy complejos que surgen a partir de un conjunto de reglas conocidas y simples.

Otro de los puntos a destacar es que a pesar de su simplicidad son muy expresivos ya que tiene la complejidad de una \textit{máquina universal de Turing}\cite{paul-conway-turing}, lo que hace que sea \textit{Turing-completo}.% Por lo que se puede usar para calcular cualquier \textit{función o lenguaje recursivo}, que según sostiene la tesis de Church-Turing \textit{"todo lo computable es computable por una máquina de Turing"}. 
%Luego, el \textit{Juego de la Vida} nos permite resolver exactamente todos los problemas que se pueden resolver por un \textit{algoritmo}.


\subsubsection{• Implementación}

El lenguaje usado fue el mismo que para las simulaciones, Python. Para la implementación de un CA se pueden usar diferentes tipos de datos. Aquí se decidió definir una clase \textit{Matrix} que guarda como atributos internos la cantidad de filas y columnas y también la matriz en si que es una lista de listas (un \textit{array} de \textit{arrays}). Cada una de las posiciones de este objeto \textit{Matrix} está ocupada por un entero, 0 o 1 según la celda esté muerta o viva respectivamente. A continuación la definición de la clase \textit{Matrix} en Python:

\begin{mylisting}
\begin{verbatim}
class Matrix():
    """Creo una matriz que sera una lista de listas
    la lista inicial tendra en cada posicion las filas
    de la matriz:
    Ejemplo de matriz 4xn
        [fila1, fila2, fila3, fila4]
    Donde fila_i es una lista de longitud n"""
    
    def __init__(self, rows, cols):
        self.cols = cols
        self.rows = rows
        
        # Inicializo matriz
        self.matrix = []
        
        for i in range(rows):
            # Creo una fila nuevo
            row = []
            
            for j in range(cols):
                # Lleno la fila con 0 en cada celda
                row.append(0)
            
            self.matrix.append(row)
\end{verbatim}
\end{mylisting}

Debido a que el cambio de estado de un CA de un momento $t$ al $t+1$ se basa en la aplicación de reglas de forma síncrona a todas las celdas de la matriz, una de las opciones de implementación para actualizar su estado es usando dos matrices, una para el tiempo $t$(\textit{matrix}) y otra para el tiempo $t+1$(\textit{new}), donde la segunda matriz (\textit{new}) obtenga los valores de cada celda a partir de recorrer todas las celdas de la matriz (\textit{matrix}) y aplicar las reglas. A continuación se muestra la función de actualización de estado de la matriz:

\begin{mylisting}
\begin{verbatim}
def update(matrix):
    new = Matrix(matrix.rows, matrix.cols)
    
    for i in range(1, matrix.rows+1):
        for j in range(1, matrix.cols+1):
            vivir = rules(matrix, i, j)
            if vivir:
                new.set_value(i,j, VIVO)
                
    return new
\end{verbatim}
\end{mylisting}

donde \textit{rules()} obtiene los vecinos \textit{vivos} de \textit{(i,j)}. Por lo tanto para actualizar \textit{matrix} basta con,

\begin{mylisting}
\begin{verbatim}
matrix = update(matrix)
\end{verbatim}
\end{mylisting}

con esto ya estamos en condiciones de implementar el \textit{Juego de la Vida} con un bucle que actualize la matriz en cada pasa de tiempo. Pero hasta aquí tenemos una matriz con ceros y unos, por lo que se decidió usar la librería PyGame para implementar el juego de la vida de forma gráfica. Para lograr esto, se hizo uso de la clase \textit{Sprites} de PyGame en la definición de una nueva clase, la clase \textit{Cell}.

\begin{mylisting}
\begin{verbatim}
# Celda de automata celular usando Sprites de Pygame
class Cell(pygame.sprite.Sprite):
    
    def __init__ (self, color=None, size=None, pos=None):
        global N, cells
        # Inicializo Sprite
        pygame.sprite.Sprite.__init__ (self) 
        
        if size == None:
            size = (SIZE,SIZE)
        image = pygame.Surface(size)
        image = image.convert()
        
        if color==None:
            # 0 = blanco, 1 = negro ; 0 = muerto, 1 = vivo
            color = 0
        self.color = color
        self.new_color = color
        # Lo lleno del color correspondiente
        if color: 
            image.fill( BLACK )
        else:
            image.fill( WHITE )
            
        self.image = image
        self.rect = image.get_rect()
        
        self.pos = (0,0)
        if pos != None:
            self.pos = pos
        self.rect.topleft = pos
\end{verbatim}
\end{mylisting}

Para mantener separada la parte numérica de la parte gráfica se creó una nueva matriz, separada, que agrupa todos los \textit{Sprites}, cuyas posición en la ventana creada es una al lado de la otra y el color que toma (blanco o negro) depende de si la celda de la matriz \textit{matrix} está muerta o viva respectivamente. Por lo tanto esta matriz de \textit{Sprites} de Pygame se adapta al estado que tiene el CA simulado numericamente.

Dentro de este autómata celular se conocen muchos patrones, los cuales viajan u oscilan dentro del juego de la vida. Unos de los más conocido son los \textit{gliders}, patrones que viajan en forma diagonal. Aquí se muestra el resultado de una ejecución que se realizón con la implementación aquí mostrada del juego de la vida donde se reproduce un \textit{disparador de gliders} o \textit{gliders gun}.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm, width=6cm]{img/glider2.eps} 
}
\caption{Captura de arma disparadora de gliders y gliders viajando en diagonal.}
\label{gliders-gun}
\end{figure}


\subsubsection{• Autómatas Celulares y presión}

%Para simular la propagación de \textit{presión} en el medio, que será necesaria para implementar un sensor de sonido para los agentes, se usó un CA. Este CA representa el medio en el que se encuentran los \textit{agentes o boids} y cada celda de este CA es una porción del sistema.

Para simular el entorno donde se propagará la \textit{presión} se usó un CA. Ahora, nuestro sistema está discretizado, i.e, un punto en el plano ahora está representado por una celda y esta celda a su vez tiene vecinos, cuya cantidad depende de la vecindad elegida. Esta forma de discretizar el sistema nos ayudará mucho para mantener un control de las propiedades del mismo y es muy útil para simular entornos en videojuegos.

Por ejemplo, si pensamos en un medio homogéneo lleno de \textit{aire} entonces cada celda representa una pequeña porción de este medio, donde todas las celdas tienen la misma propiedad. Se comportarán respetando las reglas que queremos que cumpla este medio.

También podemos modelar sistemas más complejos. Supongamos que deseamos propagar fuego o presión  por ese medio, entonces solo nos basta estudiar como es que se propaga en este medio y aplicar esas reglas para las celdas del CA. Si queremos ahora agregar paredes u otros materiales, entonces las propiedades de estas celdas son distintas donde sea que se ubiquen.

Para implementar este nuevo CA se definió en Python la clase \textit{Matrix()}. Veamos a continuación la definición del método \textit{\_\_init\_\_}

\begin{mylisting}
\begin{verbatim}
class Matrix():
    """Creo una matriz que sera una lista de listas
    la lista inicial tendra en cada posicion las filas
    de la matriz:
    Ejemplo de matriz 4xn
        [fila1, fila2, fila3, fila4]
    Donde fila_i es una lista de longitud n"""
    
    def __init__(self, rows, cols):
        '''Inicializa una matriz de NxM donde N=rows y M=cols. 
        Todas las celdas se inicializan en 0'''
        self.cols = cols
        self.rows = rows
        
        # Inicializo matriz
        self.matrix = []
        
        for i in range(rows):
            # Creo una fila nuevo
            row = []
            
            for j in range(cols):
                # Lleno la fila con 0 en cada celda
                celda = Celda()
                row.append(celda)
            
            self.matrix.append(row)
\end{verbatim}
\end{mylisting}

como se puede ver en cada lugar de la matriz hay un objeto \textit{\textbf{Celda()}}. Esta clase está definido de la siguiente manera:

\begin{mylisting}
\begin{verbatim}
class Celda():
    '''Define la clase que se usa como celda de una matriz.'''
    def __init__(self, pressure=0, new_pres=0):
        '''Inicializa todos los valores con pressure y los new con new_pressure.'''
        self.visitado = False
        self.visitas = []
        self.pressure = pressure
        self.new_pressure = new_pres
\end{verbatim}
\end{mylisting}

De esta forma dejamos definido el CA que usaremos para la propagación de presión. Ahora nos enfocaremos en el algoritmo que utilizamos.

\subsubsection{• Algoritmo}\label{subsubsection-algoritmo}
Para propagar la presión en el medio se siguió el paper \cite{ca-physical-modeling}, pues usa la noción de propagación en un CA con la aplicación de reglas a sus celdas. Tendremos una matriz cuyas celdas se relacionan con sus celdas vecinas siguiendo ciertas reglas que se deben determinar. Una posible representación gráfica de nuestro sistema a gran escala es el de la Figura \ref{matriz-ambient}.
%. En esencia, lo que se hizo fue tomar al sistema, el ambiente donde viven los agentes, como una gran matriz. Esta matriz está llena de celdas, que representan cada punto del plano del ambiente. Estas celdas son las que se relaciona entre sí y guardan la información local del sistema. En nuestro caso, la presión en ese punto.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm, width=6cm]{img/matrix-ambiente.eps} 
}
\caption{Sistema interpretado como matriz.}
\label{matriz-ambient}
\end{figure}

Como se puede notar, usando esta forma de interpretación no sería dificil extenderlo hacia un ambiente con obstáculos. Donde los obstáculos son objetos inertes que no permiten la propagación de presión. Son celdas que obstruyen la propagación normal, ya sea sea de forma total o parcial. Esto haría que el sistema no sea más de una composición homogenea. 

Para hacerlo podemos identificar celdas \textbf{vivas} de \textbf{inertes} o tener un valor que defina la cantidad de flujo que permiten pasar. Es decir, un grado de permeabilidad para las celdas. Aquí aplicamos ambas opciones en paralelo. Esto puede ser de mucha utilidad para video juegos donde se necesite modelar un medio complejo, con distintos materiales.

En la Figura \ref{matriz-ambiente} podemos ver un ejemplo de un sistema con celdas inertes que no permiten la transmisión de flujo. Notemos que se decidió usar la vecindad de \textit{Von Neumann}, i.e los vecinos al norte, sur, este y oeste de la celda.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm, width=6cm]{img/matrix-cells-inert.eps}
}
\caption{Sistema con celdas que impiden el flujo de presión. Con \textit{azul} identificamos las celdas vivas del sistema y con \textit{gris} las inertes. Podría ser una pared que obstruye el flujo de presión del aire, donde el aire se identifica con las celdas \textit{azules}.}
\label{matriz-ambiente}
\end{figure}

Para simular la propagación de presión, lo que debemos hacer es definir reglas que demuestren el comportamiento que deseamos. Claramente cada celda va a tener cierta magnitud de presión, y en la próxima generación del CA esta presión se debe propagar. Pero, ¿hacia dónde? y ¿cuánto? son preguntas que debemos definir.

El algoritmo que se siguió lo que hace es, para cada vecino de la celda, calcular primero la diferencia de presión que existe con este.  De la diferencia de presión, solo se pasará cierto porcentaje y a su vez, esta cantidad a pasar antes se mide entre un mínimo y un máximo para mantener una propagación homogenea y que nos permitan ver una evolución de nuestro entorno dinámico lo más natural posible. De esta forma mejoramos la inmersión de los usuarios en los videojuegos y la expresividad del entorno, puntos que son más que importantes en el desarrollo de videojuegos. Como podemos ver en \cite{ca-physical-modeling}, el siguiente algoritmo nos sirve para simular la propagación de presión en un CA.

\begin{mylisting}
\begin{verbatim}
for (neigh = each neighbor celll
{
    if ( neigh->Material->IsInert() ) continue;
    float DPress = cell->Pressure - neigh->Pressure;
    float Flow = cell->Material->Flow * DPress;
    Flow = clamp ( Flow, cell->Pressure / 4.0f, -neigh->Pressure / 4.0f );
    cell->NewPressure -= Flow;
    neigh->NewPressure += Flow;
	
}
\end{verbatim}
\end{mylisting}

donde la función \textit{\textbf{clamp()}} es la que regula la cantidad de flujo a pasar a los vecinos, chequeando que este flujo esté entre un \textit{\textbf{mínimo}} y un \textit{\textbf{máximo}}. Podríamos implementar \textit{\textbf{clamp()}} de la siguiente forma:


\begin{mylisting}
\begin{verbatim}
def clamp(value, max, min):
        '''
        Funcion clamp, devuelve value si value esta entre min y max, devuelve min o max si no.
        '''
        if value<min:
            return min
        if value>max:
            return max
        return value
\end{verbatim}
\end{mylisting}        

Como podemos ver, el algoritmo para la propagación de presión es suficientemente simple. La división por 4 que se hace en el algoritmo de cálculo de flujo es debido a que son 4 los vecinos que se están usando, por la vecindad de Von Neumann. De esta forma, nos aseguramos de tener siempre flujo para pasarle a nuestros vecinos. Otros casos de elección de vecinos podrían ser:
\begin{itemize}
\item En 2D, los 8 vecinos de la vecindad de Moore.
\item En 3D, los 6 vecinos que comparten la cara con el cubo central.
\item En 3D, los 6 anteriores más 12 que comparten un borde con el cubo central.
\item En 3D, los 18 anteriores más 8 que comparten una esquina con el cubo central.
\end{itemize} 

Recordemos que el algoritmo de actualización de presión que vimos se debe correr para cada celda del CA. Para hacer un recorrido de la matriz más óptimo se usa una variable que guarde el estado futuro de la presión. Si se actualizara la presión de cada celda cuando se calcula su nueva presión entonces la presión de una celda se propagaría en la dirección que se recorra la matriz del CA. Situación que debemos evitar.

Para el ambiente que se desea simular, que se supone homogeneo, necesitamos que la presión se distribuya de la forma más natural posible, similar a la onda que se genera en una superficie de agua por la aplicación de presión en un punto. Este tipo de ondas se propagan a una velocidad característica en todas las direcciónes. Para esto es que necesitamos recorrer una vez el CA para actualizar la presión y guardar este dato en una variable aparte y luego recorrer de nuevo el CA para actualizar los valores de presión, i.e, seguir el siguiente algoritmo.


\begin{mylisting}
\begin{verbatim}
for ( celll in matrix)
{
    cell->Pressure = cell->NewPressure;
}
\end{verbatim}
\end{mylisting}


\subsubsection{• Implementación}\label{subsection-ca-implementacion}
La implementación de este CA fue mediante dos clases principales, la clase \textbf{Matrix()} y la clase \textbf{Celda()}. Como vimos antes, en el \textit{Juego de la Vida}, la clase \textbf{Matrix()} tiene como atributos la matriz en si que define el CA, que es un \textit{array de arrays} donde en cada posición hay un objeto del tipo \textbf{Celda()}.

Veamos la clase \textbf{Matrix()} y \textbf{Celda()}:

\begin{mylisting}
\begin{verbatim}
class Matrix():
    """Creo una matriz que sera una lista de listas
    la lista inicial tendra en cada posicion las filas
    de la matriz:
    Ejemplo de matriz 4xn
        [fila1, fila2, fila3, fila4]
    Donde fila_i es una lista de longitud n"""
    
    def __init__(self, rows, cols):
        '''Inicializa una matriz de NxM donde N=rows y M=cols. 
        Todas las celdas se inicializan en 0'''
        self.cols = cols
        self.rows = rows
        
        # Inicializo matriz
        self.matrix = []
        
        for i in range(rows):
            # Creo una fila nuevo
            row = []
            
            for j in range(cols):
                # Lleno la fila con 0 en cada celda
                celda = Celda()
                row.append(celda)
            
            self.matrix.append(row)
            
class Celda():
    '''Define la clase que se usa como celda de una matriz.'''
    def __init__(self, pressure=0, new_pres=0):
        '''Inicializa todos los valores con pressure y los new con new_pressure.'''
        self.pressure = pressure
        self.new_pressure = new_pres
\end{verbatim}
\end{mylisting}

estos son solo los métodos \textit{\textbf{\_\_init\_\_()}} de las clases.

Pero como vimos antes, necesitamos alguna forma de actualización de la matriz. Esto es, ¿cómo el CA va a cambiar del estado actual al estado de la generación siguiente? Para esto la clase \textbf{Matrix()} tiene un método que aplica la regla de propagación de presión que vimos anteriormente. El método se llama \textbf{rules()} y se implemntó como sigue:

\begin{mylisting}
\begin{verbatim}
def rules(self):
        '''
        Recorro la matriz. Para cada vecino de la celda:
            1) Obtengo la diferencia de presion 
            2) Uso la funcion clamp() para ajustar el valor a pasar
            3) Transfiero el valor a la celda vecina (a new_pressure)
            4) Resto lo que transferi a la celda que estoy visitando
        '''
        flow = 0.15
        
        for i in range(1, self.rows+1):
            for j in range(1, self.cols+1):
                
                # Obtengo la celda y la marco visitada
                celda = self.get_cell(i,j)
                
                # Obtengo los vecinos de neumann (4 vecinos)
                vecinos = self.vecinos_neumann(i,j)
                
                # Actualizo puntos cardinales
                for punto, vecino in vecinos.items():
                    
                    # Obtengo la diferencia de presion
                    dpres = celda.get_pressure() - vecino.get_pressure()
                    
                    # Ajusto el valor a transferir
                    valor = clamp (flow*dpres, celda.get_pressure()/4, -vecino.get_pressure()/4)
                    
                    # Transfiero el valor al vecino
                    vecino.update_new_pressure( valor)
                    
                    # Resto lo que transferi
                    celda.update_new_pressure(-valor)
                    
        return 
\end{verbatim}
\end{mylisting}

donde \textbf{\textit{flow}} es una constante que define el grado de propagación del medio. Un valor muy chico hará que el flujo transmitido de una celda a sus vecinas sea muy poco, haciendo que la propagación sea más lenta. Por lo tanto, esto podemos adaptarlo según el medio que necesitemos simular.

Luego de llamar a este método, será necesario actualizar los valores de la matriz. Para esto llamamos al método \textbf{\textit{update\_matrix()}} que es tan simple como sigue.

\begin{mylisting}
\begin{verbatim}
def update_matrix(self):
        
        for i in range(1, self.rows+1):
            for j in range(1, self.cols+1):
                self.get_cell(i,j).update()
                
        return 
\end{verbatim}
\end{mylisting}

donde vemos que se llama al método \textit{\textbf{update()}} de la clase celda para cada celda de la matriz. Veamos el método \textit{\textbf{update()}}.

\begin{mylisting}
\begin{verbatim}
def update(self):
        '''Actualiza pressure con el valor de new_pressure.'''
        self.pressure = self.new_pressure
\end{verbatim}
\end{mylisting}

Las clases que vimos y los métodos de las mismas nos permitirán poder simular propagación de presión en nuestro CA. Lo que hará el algoritmo principal será inicializar la matriz del tamaño que sea requerido, con los valores iniciales de presión que se desee, luego bastará con un blucle que actualize la presión con un algoritmo como el visto. Por cuestiones de optimización, se puede tener una variable que guarde el tiempo de actualización de cada celda, de modo que cuando este tiempo sea distinto al actual se actualiza el valor de presión de la celda. Esto nos permite optimizar la actualización ya que un solo recorrido de la matriz se encargará tanto de calcular el nuevo valor de la presión como de actualizarlo realmente si es necesario.

De esta forma queda un algoritmo de actualización como el siguiente:

\begin{mylisting}
\begin{verbatim}
def rules_pressure(self):

        for i in range(1, self.rows+1):
            for j in range(1, self.cols+1):

                ''' si la celda no esta actualizada, actualizarla '''
                if self.get_cell(i,j).t != self.t:
                    self.get_cell(i,j).t= self.t
                    self.get_cell(i,j).update()
                    
                ''' loop sobre todos los vecinos'''    
                vecinos = self.vecinos_neumann(i,j)
                total_vecinos = float(len(vecinos))
                
                for vecino in vecinos:
                    ''' si la celda no permite el flujo, sigo '''
                    if not vecino.allow_flow:
                        continue
                    ''' si el vecino no esta actualizado, lo actualizo '''    
                    if vecino.t != self.t:
                        vecino.t= self.t
                        vecino.update()
                        
                    ''' Calculo la diferencia de presion '''
                    dpres = self.get_value(i,j) - vecino.get_pressure()
                
                    '''Calculamos el flujo como una fraccion de la diferencia de presion.
                    0.12 es un numero magico que indica la fluidez del medio. Un valor muy chico
                    hace que la presion se propague mas lentamente.
                    Usamos la funcion clamp para evitar valores negativos en el nodo.
                    Se hace que el flujo no produsca una presion negativa'''
                    flow = self.get_cell(i,j).porosidad*dpres
                    maxFlow = self.get_value(i,j)/total_vecinos
                    minFlow = -vecino.get_pressure()/total_vecinos
                                        
                    ''' prevenimos flujo mayor a la presion actual '''
                    flow=clamp(flow,maxFlow,minFlow)
                  
                    '''Actualizamos la presion (usando new_pressure en lugar de 
                    pressure) substrayendo presion del nodo actual y agregandola
                     a su vecino. Un flujo negativo implica que la presion del 
                     nodo actual aumenta y la del vecino disminuye.'''
                    self.get_cell(i,j).new_pressure -= flow
                    vecino.new_pressure += flow
        self.t  +=  1
        return self.t
\end{verbatim}
\end{mylisting}

A continuación mostraremos en la Figura ~\ref{evolucion-explosion} algunos snapshots de la evolución de una propagación de presión en un entorno dinámico simulado con las técnicas aquí vistas. Donde también se incluyó paredes (en rojo) que no permiten el flujo de presión através de ellas.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=4.5cm, width=0.95\textwidth]{img/evolucion-2010-11-20-explosion5.eps} 
}
\caption{Evolución del flujo de presión en entorno dinámico con paredes(rojo) que impiden el flujo de presión.}
\label{evolucion-explosion}
\end{figure}

\newpage
\subsection{Acoplamiento de Agentes y Entorno Dinámico}\label{subsection-acoplamiento}

Ahora que hablamos e implementamos técnicas de flocking para agentes autónomos y también de la implementación de entornos dinámicos usando autómatas celulares, mostraremos una forma de acoplar ambas soluciones. Para esto debemos tener en cuenta que por un lado tenemos a los agentes, los cuales ``viven'' o ``se mueven'' en un espacio continuo, y por otro lado tenemos a nuestro entorno dinámico, el cual está caracterizado por un espacio discreto. Para entender mejor la situación planteada veamos el esquema de la Figura \ref{entorno-continuo-discreto}.


\begin{figure}[h!t]
\centerline{
   \includegraphics[height=4cm, width=6.5cm]{img/CA-continuo-discreto.eps} 
}
\caption{Esquema de respresentación del mundo continuo y discreto}
\label{entorno-continuo-discreto}
\end{figure}

Aquí se muestra una forma de representación de objetos estáticos en el espacio del video juego, el cual es considerado continuo, pero modelado según una grilla del CA que simula este entorno dinámico de modo discreto. 

En la Figura \ref{entorno-continuo-discreto}, las celdas oscuras no son actualizadas por el CA, son celdas inertes a través de las cuales la presión no se propaga. Estas celdas inertes son de fácil representación en nuestro CA ya que basta con setear la propiedad de la celda que dice si son inertes o no. Vimos una simulación de esto en la Figura \ref{evolucion-explosion} de la sección \ref{subsubsection-algoritmo}.

Las celdas que representan a un objeto se seleccionan utilizando el \textit{bounding box} de cada objeto. El bounding box es la caja de menor área que encierra completamente la base del objeto, es decir, todas las celdas contenindas en el bouding box son consideradas inertes. Podemos ver una ilustración de lo aquí explicado en la Figura \ref{bounding-box1}.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm, width=6cm]{img/bounding-box1.eps} 
}
\caption{Bounding box de un agente en el entorno dinámico.}
\label{bounding-box1}
\end{figure}

Por otro lado, tenemos a los agentes, que se mueven en el espacio continuo. Su actualización de posiciones puede hacerse en base a velocidad y fuerza o en base a su posición. Si se basa en velocidades y aceleraciones es necesario implementar un integrador, o en otras palabras, necesitamos un motor de física. En la actualidad existen bibliotecas de acceso libre de muy buena calidad: 2D, rescatamos Chipmunk\cite{chip}, por su simplicidad y facilidad de programación; en 3D, los motores suelen ser más complicados y el emblema de la comunidad libre de hoy es Bullet Physics\cite{bullet}. Es posible prescindir de integradores basados en velocidad e implementar la física utilizando únicamente las posiciones de los agentes\cite{Muller2007109}. La integración con dichos motores es algo que sería interesante ver en un trabajo futuro.%  Sin embargo, no tenemos experiencia con estos motores. 

En este trabajo se eligió utilizar movimientos basados en fuerzas. Está elección facilita el acoplamiento de los agentes con el CA subyacente. Al igual que los objetos estáticos, los agentes son representados en el espacio discreto utilizando la proyección de su bounding box, como vimos en la Figura \ref{bounding-box1}. La fuerza sobre el agente, causada por las ondas de presián fluyendo en el CA, se calcula en base a las diferencias de presión sobre los lados del agente, como se muestra en la Figura \ref{bounding-box-fuerza}. Es decir, la componente horizontal de la fuerza está dada por la diferencia entre la presión en los lados izquierdo y derecho. Mientras que la componente vertical viene dada por la diferencia de presión entre las celdas superiores e inferiores del bounding box del agente. En ecuaciones podemos escribir como \eqref{eq:dP}.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm, width=0.95\textwidth]{img/Castro_Carbajal_Fig3.eps} 
}
\caption{Bounding box del agente y cálculo de fuerza.}
\label{bounding-box-fuerza}
\end{figure}

\begin{equation}
\begin{split}
\begin{aligned}
\label{eq:dP}
p_j &=& \sum_i \vert p_{ij} \vert \quad j=\mathsf{u,d,l,r} \\
\vec{F} &=& \left( p_u - p_d, p_l -p_r \right).
\end{aligned}
\end{split}
\end{equation}

\noindent Donde $\mathsf{u,d,l,r}$ indican arriba, abajo, izquierda y derecha, respectivamente. La presión en cada celda se denomina $p_{ij}$, donde el subíndice $i$ recorre las celdas del lado correspondiente. Tomamos el valor abosluto, dado que los valores de $p_{ij}$ pueden ser negativos, de esta manera la suma refleja la ''activitad" del CA. Si se omite, el efecto de la presión sobre el agente es menor. El signo de las diferencias en la ecuación (\ref{eq:dP}) depende de las convenciones utilizadas y pueden variar seg\'un la implementaci\'on. 

También en este acoplamiento se puede lograr afectar el entorno dinámico y no solo sensarlo. Por ejemplo, si quisiéramos que nuestros agentes afectaran con presiones al entorno en cada punto donde se encuentran entonces podría ser buena práctica tomar su bounding box y dotar de una cantidad determinada de presión extra a cada celda del perímetro de su bounding box.

Pero esta no es la única forma, ya que también se podría haber optado por dotar de presión extra solo a la celda del centro de su bounding box. Aquí se aconseja usar la primera opción en base a pruebas empíricas de la propagación de la presión realizadas. 

Esto que vimos, se puede aplicar para afectar el entorno de distintas maneras(calor, sonido, etc.), por lo que el lector tiene libertad para probar y elegir la forma que mejor se adapte a sus necesidades.

\newpage
\section{•Resultados}
En esta sección incorporamos resultados obtenidos con los modelos antes vistos. Comenzaremos con algoritmos de rebaño de tipo continuos y discretos para luego avanzar con las integraciones de sensores y entornos dinámicos.


\subsection{•Algoritmos de rebaño de tipo discreto}
Veremos a continuación algunas imágenes de simulaciones hechas con netlogo, aplicando el algoritmo visto \ref{sectionNetLogo}.

\begin{figure}[ht!]
	\centering
   	% ----primer subfigura----
	\subfloat[Setup de simulación.]{
	\label{netLogo-simulation1:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{img/netLogo-img1-screen.eps}}
	% ----segunda subfigura----
	\subfloat[Simulación a los 100 ticks de tiempo.]{
	\label{netLogo-simulation1:b}         %% Etiqueta para la segunda subfigura
	\includegraphics[width=0.55\textwidth]{img/netLogo-img2-screen.eps}}%\\[20pt]
	
%\end{figure}

%\begin{figure}[ht!]

	%\centering
   	% ----primer subfigura----
	\subfloat[Simulación a los 248 ticks de tiempo.]{
	\label{netLogo-simulation1:c}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{img/netLogo-img3.eps}}
	% ----segunda subfigura----
	\subfloat[Simulación a los 499 ticks de tiempo.]{
	\label{netLogo-simulation1:d}         %% Etiqueta para la segunda subfigura
	\includegraphics[width=0.55\textwidth]{img/netLogo-img5.eps}}\\[20pt]
   	\caption{Simulacion hecha en NetLogo basada en los algoritmos aquí propuestos. Con los parámetros de population=150 turtles, vision=5.00 patches, minimum-separation=1.00 patches, max-align-turn=5.00 degrees, max-cohere-turn=3.00 degrees, max-separate-turn=1.50 degrees.}
   	\label{netLogo-simulation1}                %% Etiqueta para la figura entera
\end{figure}

En la figura \ref{netLogo-simulation1} vemos una simulación hecha con 150 turtles distribuidas al azar, donde cada turtle tenía un rango de visión de 5 patches. Por lo tanto, aquí una turtle solo será afectada por otras turtles que entén hasta una distancia de 5 patches. De su grupo de vecinos, la turtle deberá calcular el vecino más cercano, el cual si se encuentra a una distancia menor a 1 patch lo obligará a aplicar la regla de separación. De otro modo, la turtle intentará agruparse y alinearse con sus vecinos teniendo en cuenta los límites seteados.


\subsection{•Algoritmos de rebaño de tipo continuo}

A continuación veremos capturas de simulaciones hechas para todas las regiones del prototipo implementado y estudiado en \ref{section-modelos-continuos}. 

\begin{itemize}
\item Región I: En esta región se forman grupos de agentes que viajan en forma circular al rededor de su centro de masa. Todos los agentes de un grupo tienen velocidades paralelas entre si y equivalentes a las de los demás agentes del sistema siendo la media $|v_i|^2 \sim \alpha / \beta$. Pero esta es una región catastrófica, lo que implica que a medida que el número de agentes crece $N \rightarrow \infty$ los agentes tienden a converger hacia un punto, debido al aumento de la fuerza de atracción. Vemos una captura de una simulación obtenida de esta región en la Figura \ref{region-i}.
\begin{figure}[h!t]
\centerline{
   \includegraphics[height=7cm]{img/R_I2009_10_1_17_23_36.eps} 
}
\caption{Región I. Parámetros: $N = 150; C_a = 1.0 ; C_r = 0.6 (C < 1)$ y $l_a = 1.0 ; l_r = 0.5 (l<1)$ con $\alpha = 1.0$ y $\beta = 0.5$.}
\label{region-i}
\end{figure}

\item Región II: Esta región también es catastrófica. Aquí $C = l$, y como vemos en Figura \ref{regiones} el patrón esperado es un círculo, cuyo radio disminuirá a medida que N crece. En Figura \ref{region-ii} vemos una captura de nuestra simulación para esta región.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=7cm]{img/R_II2009_10_5_15_59_58.eps} 
}
\caption{Región II. Parámetros: $N = 40; C_a = 1.0 ; C_r = 0.8$ y $l_a = 1.0 ; l_r = 0.8$ con $ \alpha = 1.0 ; \beta = 1.5$.}
\label{region-ii}
\end{figure}

\item Región III: Ésta región es catastrófica, con $ l > C$. Aquí aparecen grupos aunque no hay una separación bien definida entre los agentes. Estos se mueven siguiendo un patrón similar a un anillo. En Figura \ref{region-iii} vemos una captura de nuestra simulación.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=7cm]{img/R_III2009_9_30_20_52_10.eps} 
}
\caption{Región III. Parámetros: $N = 40; C_a = 1.0 ; C_r = 0.4$ y $l_a = 1.0 ; l_r = 0.7$ con $ \alpha = 1.0 ; \beta = 0.5$.}
\label{region-iii}
\end{figure}

\item Región IV: Ésta es otra región catastrófica, y como en el caso anterior $l > C$ pues ${C < 1 < l}$. Aquí vemos a los agentes agruparse y alinear su vector velocidad a una velocidad característica.
\begin{figure}[h!t]
\centerline{
   \includegraphics[height=7cm]{img/R.IV2009_9_30_22_20_46.eps} 
}
\caption{Región IV. Parámetros: $N = 40; C_a = 1.0 ; C_r = 0.4$ y $l_a = 1.0 ; l_r = 2.0$ con $ \alpha = 1.0 ; \beta = 0.5$.}
\label{region-iv}
\end{figure}

\item Región V: Aquí tenemos que $max \lbrace C,l \rbrace > 1$ y corresponde a una región H-estable. Aquí el potencial entre partículas del sistema se caracteriza por su componente de repulsión, minimizándose este cuando la $d_ij \rightarrow \infty$. Por lo que se espera que las partículas tiendan a divergir. En Figura \ref{region-v} vemos una captura de nuestra simulación.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=7cm]{img/R_V2009_10_1_17_30_6.eps} 
}
\caption{Región V. Parámetros: $N = 100; C_a = 0.5 ; C_r = 2.0 $ y $l_a = 0.5 ; l_r = 1.5$ con $ \alpha = 1.6 ; \beta = 0.5$.}
\label{region-v}
\end{figure}

\item Región VI: En esta región $ \lbrace 1/ \surd C < l < 1 \rbrace$. Es una región H-estable y en donde para un número finito de N, y valores intermedios de $\alpha / \beta$, las partículas ganan una energía cinética que es mucho mayor a la interacción entre partículas. Por lo que las partículas tienden a separarse. Por otro lado, para valores pequeños de $\alpha / \beta$ se espera que las partículas se organicen con separaciones bien definidas entre partículas.  En Figura \ref{region-vi} vemos una captura de nuestra simulación.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=7cm]{img/R_VI2009_10_6_15_21_51.eps} 
}
\caption{Región VI. Parámetros: $N = 100; C_a = 1.0 ; C_r = 2.0$ y $l_a = 1.0 ; l_r = 0.8$ con $ \alpha = 1.0 ; \beta = 0.5$.}
\label{region-vi}
\end{figure}

\item Región VII: En esta región $ \lbrace l < 1/ \surd C < 1 \rbrace$. Es una región catastrófica y como tal, cuando $N \rightarrow \infty $ el sistema converge. Pero para valores intermedios de $\alpha / \beta$ las partículas se mueven formando una dona, i.e, confinadas dentro de 2 radios(uno interno y uno externo). Estas partículas, para valores finitos de N, se pueden mover en sentido horario y anti-horario (coexistiendo ambos), dependiendo de las condiciones iniciales. En Figura \ref{region-vii} vemos una captura de nuestra simulación, donde se pueden ver dobles espirales, horarios y anti-horarios, que son un indicador de un potencial catastrófico.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=7cm]{img/R_VII2009_10_6_15_24_42.eps} 
}
\caption{Región VII. Parámetros: $N = 100; C_a = 0.5 ; C_r = 1.0$ y $l_a = 2.0 ; l_r = 0.5$ con $ \alpha = 1.6 ; \beta = 0.5$.}
\label{region-vii}
\end{figure}
\end{itemize}

Si analizamos las pruebas del prototipo, creemos que son positivas. Los tiempos de convergencia no fueron altos, entre 10 y 15 segundos y la codificación no tiene un alto nivel de complejidad. Hay que tener en cuenta que aquí las condiciones iniciales de los agentes fueron posiciones $(x,y)$ al azar dentro de un círculo con radio $R$ y velocidades al azar. 

También cabe destacar que los agentes se movían dentro de un espacio abierto, y el poder lograr que se auto-organizen sin haber codificado sus movimientos específicos es un caso de éxito ya que lo mismo se puede usar para agentes de videojuegos que quisiéramos agrupar o formaciones que los mismos deben adoptar. %Claro que también las aplicaciones se extienden a otras ramas, como simulaciones de comportamientos o creación de boids para su agrupación, como envío masivo de satélites pequeños al espacio y que los mismos se organizen para funcionar como un grupo.

El prototipo aquí presentado puede extenderse también al uso de otros potenciales, y no solo interacciones del tipo soft-core. Los resultados dependerán de los potenciales utilizados y la parametrización de los mismos. También notamos que la parametrización no tiene por que ser fija, ya que se pueden usar parametrizaciones que hagan diverger a los agentes para que los mismos tengan un comportamiento de búsqueda (ej: agentes en un mapa de videojuego que deban hacer reconocimiento de terrenos, ya sea en búsqueda de enemigos, comida, materiales o algún objeto preciado) y luego se los puede re-parametrizar para que tengan un comportamiento de convergencia. De esta forma, nuestros agentes podrían pasar de situaciones H-stable a catastróficas y viceversa.


\subsubsection{• Simulaciones con sensor de visión}
Lo que usamos para definir la relación entre los agentes sigue siendo el potencial de Morse. Pero ahora, usando la visión se acota el alcance de la función. Las simulaciones hechas fueron especialmente sobre la \textit{región catastrófica VII}. Para cada conjunto de parámetros que se eligieron, se hicieron dos tipos de simulaciones: \textit{con visión} y \textit{sin visión}. De modo que podamos comparar los resultados obtenidos. Veremos a continuación los patrones que emergen de estas simulaciones.

\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{snapshot1:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_4_21_35_32_snapshot_con_vision_n100.eps}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{snapshot1:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_7_17_20_55_snapshot_sin_vision_n100.eps}}\\[20pt]
	\caption{Patrones de simulaciones de la \textit{región VII} de \cite{self-propelled-particle}. Parámetros para ambos: $C_a = 0.5 ; C_r = 1.0 ; l_a = 2.0 ; l_r = 0.5 ; \alpha = 1.6 ; \beta = 0.5$ y N=100(cantidad de agentes).}
   	\label{snapshot1}                %% Etiqueta para la figura entera
\end{figure}

Lo que podemos notar en la Figura \ref{snapshot1:a} es que con visión, para los parámetros elegidos de la región VII de \cite{self-propelled-particle}, lo que antes era catastrófico ha dejado de serlo. Mientras que sin visión, como vemos en Figura \ref{snapshot1:b} sigue siendo catastrófico y emerge el mismo patrón que en la región VII de \cite{self-propelled-particle}.

También se hizo un análisis de las distancias de los agentes en ambos casos. Para esto, se hicieron histogramas con distancias entre los agentes cada intervalos regulares de tiempo. Estos histogramas están normalizados, i.e, la cuenta de los agentes en un bin está normalizada para formar una densidad de probabilidad. Esto se hizo para ver el comportamiento de la distribución de la densidad en cada caso a lo largo del tiempo. Como podemos ver en la Figura \ref{dist-time:a}, la distribución de los histogramas tiende a estabilizarse en el tiempo, aunque los agentes divergen.

%a medida que la distancia entre dos agentes se hace mas grande la probabilidad disminuye porque el area es mas grande...por lo tanto hay que dividir el calculo contra la distribucion correspondiente a puntos al azar... es medio complicado de explicar, pero si lees las paginas que te mande deberias poder cazar un poco...sino te explico de nuevo otro dia   la idea es la siguiente. Si los puntos estan distribuidos al azr, nos gustaria ver la distribucion uniforme

%Dado que tenemos una función de densidad de probabilidad, la integral del histograma debería ser 1. Esto se hizo para ver como se comporta la distribución de la densidad en cada caso a lo largo del tiempo.
\begin{figure}[ht!]
	\centering
   	% ----primer subfigura----
	\subfloat[Simulación con visión.]{
	\label{dist-time:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_4_21_35_32_log_Dist_vs_Time_con_vision_n100.eps}}
	% ----segunda subfigura----
	\subfloat[Simulación sin visión]{
	\label{dist-time:b}         %% Etiqueta para la segunda subfigura
	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_7_17_20_55_log_Dist_vs_Time_sin_vision_n100.eps}}\\[20pt]
   	\caption{Plot de distancia entre histogramas vs tiempo. Los patrones de simulaciones son idem Figura \ref{snapshot1}.}
   	\label{dist-time1}                %% Etiqueta para la figura entera
\end{figure}



\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{snapshot2:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]
	{img/R_VII2009_11_11_16_52_39_n150.eps}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{snapshot2:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]
  	{img/R_VII2009_11_12_16_18_58_sin_vision_n150.eps}}\\[20pt]
	\caption{Patrones de simulaciones de la \textit{región VII} de \cite{self-propelled-particle}. Parámetros para ambos: $C_a = 0.5 ; C_r = 1.0 ; l_a = 2.0 ; l_r = 0.5 ; \alpha = 1.6 ; \beta = 0.5$ y N=150(cantidad de agentes).}
   	\label{snapshot2}                %% Etiqueta para la figura entera
\end{figure}
A continuación se realizó una simulación con \textit{N=150} agentes para ver si el aumento de la cantidad de agentes compensaba el efecto de la visión. En la Figura \ref{snapshot2:a} podemos ver que con los parámetros usados y sensor de visión se deja de formar el patrón que antes se formaba. Por otro lado, si quitamos la visión (Figura \ref{snapshot2:b}) vemos como se comienza a formar la dona característica de dicha región.

Con respecto a la distribución de los agentes, vemos en la Figura \ref{dist-time2:a} que en la simulación \textit{con visión} la distancia entre histogramas tiende a 0, estabilizándose. Esto posiblemente se deba a la escasa energía cinética que hay en el sistema (150 agentes). Se puede notar en un principio porque los vectores que representan a los agentes son sus vectores velocidad. Por otro lado, en la Figura \ref{dist-time2:b} vemos una función con \textit{picos} en los primeros segundos, que indican cambios abruptos de la distribución de los agentes en el sistema para luego continuar con cierto ruido. Si bien estrictamente no se estabiliza la función, los rangos de oscilación son muy pequeños.
\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{dist-time2:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_11_16_52_39_log_Dist_vs_Time_con_vision_n150.eps}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{dist-time2:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_12_16_18_58_log_Dist_vs_Time_sin_vision_n150.eps}}\\[20pt]
	\caption{Distancia entre histogramas vs tiempo de la \textit{región VII} de \cite{self-propelled-particle}. Parámetros idem Figura \ref{snapshot2}.}
   	\label{dist-time2}                %% Etiqueta para la figura entera
\end{figure}


A continuación veamos la energía cinética media del sistema ($\overline{K}$). La Figura \ref{kinetic2:a} nos muestra que con visión la energía cinética tiene a bajar, acorde con la falta de velocidades que vimos en en la Figura \ref{snapshot2:a}, con 150 agentes. Mientras que en la Figura \ref{kinetic2:b} vemos una tendencia a la suba de la energía cinética con una oscilación cuyo rango decrece con el tiempo. Esto nos dice que podemos esperar una estabilización de la energía cinética media marcada por un rango de oscilación acotado.

\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{kinetic2:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_11_16_52_39_log_k_vs_time_con_vision_n150.eps}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{kinetic2:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_12_16_18_58_log_k_vs_time_sin_vision_n150.eps}}\\[20pt]
	\caption{Energía cinética vs tiempo de la \textit{región VII} de \cite{self-propelled-particle}. Parámetros idem Figura \ref{snapshot2}.}
   	\label{kinetic2}                %% Etiqueta para la figura entera
\end{figure}

También se analizaron los radios medios de los agentes, los cuales se calcularon teniendo en cuenta su centro de masa, ver Figura \ref{radiusCalc}. 

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm, width=6cm]{img/RadiusCalc.eps} 
}
\caption{Ejemplo de cálculos de radios de los agentes.}
\label{radiusCalc}
\end{figure}


En la Figura \ref{radio2:a} vemos que en un primer momento los agentes comenzaron a converger a un punto, comportamiento que indica una situación catastrófica del sistema. Pero luego hay un cambio muy abrupto en el comportamiento del sistema, después de los 2 segundos, que hace que los agentes divergan. Aunque la distancia media del radio final es suficientemente chica, lo cual quiere decir que los agentes están muy agrupados, vemos que su tendencia es a alejarse(diverger) y no a mantener un R medio estable, i.e., formar la figura de la dona.

Sin embargo, en la Figura \ref{radio2:b} vemos como el R medio oscila entre un rango definido de valores. Pero de a poco esa oscilación se va haciendo más pequeña, tendiendo hacia cierta estabilidad del R medio, propiedad necesaria para la formación de la figura de la dona, acorde al patrón de la región VII de \cite{self-propelled-particle}. La oscilación nos muestra una posible expansión y compresión de la dona, dentro de un \textit{r\_min} y un \textit{r\_max}.
 
\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{radio2:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_11_16_52_39_log_r_vs_time_con_vision_n150.eps}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{radio2:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{img/R_VII2009_11_12_16_18_58_log_r_vs_time_sin_vision_n150.eps}}\\[20pt]
	\caption{Radio medio entre agentes vs tiempo de la \textit{región VII} de \cite{self-propelled-particle}. Parámetros idem Figura \ref{snapshot2}.}
   	\label{radio2}                %% Etiqueta para la figura entera
\end{figure}

\subsubsection{• Obervaciones}
De las simulaciones hechas destacamos que fue posible reproducir los resultados de \cite{self-propelled-particle} con el algoritmo basado unicamente en el potencial de Morse. Pero también debemos destacar que cuando se quizo acotar el dominio de aplicación de dicho algoritmo y tratar de mantener el patrón de una región en particular, no se pudo lograr. %Para hacer esto se hicieron varias simulaciones con distintos parámetros de cantidades de agentes y amplitudes de visión. %Hay un caso que hay que diferenciarlo y es el de darle a los agentes un rango de visión muchas veces mayor a su separación incial y una amplitud de visión de 360° ya que aquí las condiciones no nos permiten acotar el dominio de la función, sino que nos da el mismo conjunto.

Con una visión cuya amplitud sea menor a 360° y que efectivamente acota el dominio de la función se vió que lo que era antes catastrófico ahora deja de serlo, en la región VII, ya que nos interesaba poder reproducir la formación de la dona. Para esto se intento comenzar con un sistema sin visión que formada dicho patrón y aplicar el sensor de visión con distintos rangos de amplitudas, elegidos siempre usando una búsqueda binaria, que nos permita mantener la formación. 

Estas simulaciones no lograron mantener la formación, solo compartían una evolución similar al principio y pronto las simulaciones con visión terminaban por diverger, al contrario que las simulaciones sin visión. Luego se quizo comenzar de una situación de divergencia de los agentes, para recuperar su convergencia usando nuestro sensor de visión, pero no fue posible lograr recuperar la formación. Pudimos medir algo que suponíamos, que es la disminución general de la energía cinética del sistema. Esto se puede explicar ya que los agentes ven menos vecinos y por lo tanto son afectados por menos vectores de fuerza de atracción y repulsión.

Algo que podemos concluir de las simulaciones es que el agregado de un sensor extra a un algoritmo de flocking de este tipo lo afecta lo suficiente como para no poder predecir mismos patrones que en el algoritmo original para parametrizaciones del potencial fijas. Dejando un posible trabajo futuro de redefinición de regiones con uso de potenciales y sensores.





\subsection{• Agentes Autónomos y Entornos Dinámicos}

Con los distintos modelos que hemos estudiado hasta este punto (discretos y continuos) y el estudio del entorno de los agentes autónomos, se propone entonces, como aporte para el desarrollo de videojuegos o simulaciones realista el acople de modelos discretos basados en regla con entornos dinámicos basados en CA. Propuesta que se defendió con un paper en la conferencia WAVi (Workshop Argentino de videojuegos) realizada en Diciembre del 2010 en la Ciudad Autónoma de Buenos Aires \cite{wavi2010}.

Allí expusimos un prototipo del acople de agentes autónomos, cuyo flocking se basaba en un modelo discreto de reglas, y un entorno dinámico, cuya simulación se hacía mediante un CA con reglas evolutivas como se ilustró en la sección anterior.

Para la conferencia se trabajó, con el lenguaje Python y las librerías Pygame y Numpy, en nuevas librerías que se encarguen de la simulación por un lado del entorno dinámico y por otro lado de las reglas que rigen el comportamiento de los agentes. 

La simulación del entorno dinámico se decidió implementarla en un módulo independiente usando una matriz, y se desarrollaron en un principio dos soluciones, una gráfica con Pygame para las simulaciones online y una numérica para simulaciones offline. Por otro lado, para la simulación de los agentes se creó otro módulo independiente que defina la clase del agente y tenga un método donde aplique las reglas de flocking del modelo discreto antes visto.

Estos dos módulos se acoplaron mediante un script que los incluye. No olvidar que al momento de testear el acople de ambos debemos tener en cuenta que un módulo se basa en una matriz de celdas, por lo que tiene definida cierta dimensión (la de la matriz), aunque no esté definida la unidad de medida de las celdas. Mientras que el módulo que se encarga de los agentes no supone la existencia de un espacio concreto o definido, más bien se encarga simplemente del comportamiento de los agentes. Esto se hizo para mantener una generalidad para futuros usos del módulo de los agentes autónomos.

Sin embargo, al usar Pygame, tanto el entorno dinámico (CA) como los agentes debían ser graficados con posiciones en el screen creado. Para hacer esto se propone que primero se defina un tamaño en pixeles para las celdas de la matriz, esto se hace seteando el valor de una constante global, digamos un tamaño $p$. Seguido a esto debemos definir el tamaño del entorno dinámico que deseamos, esto es, las filas y columnas que se usarán para la matriz de simulación, digamos que sea $n * m $(donde $n$ son las filas y $m$ son las columnas de la matriz). Luego podemos crear un escenario que tendrá un tamaño en pixeles de $(p * n)*(p * m)$. 

Por último nos falta situar a los agentes, cuya posición se puede definir con un par de coordenadas $(x,y)$ que definan su centro. Esto se puede lograr generando pares $(x,y)$ al azar donde $x \in [0,(p * n)]$ e $y \in [0, (p * m)]$. Luego, si quisieramos representar el centro del agente pero en nuestra matriz $n * m$ solo falta tomar cada coordenada de su posición graficada en pixeles y dividira  por $p$.

Con esto nos basta para mapear la posición de los agentes en el CA. Algo similar se hizo para obtener el bounding box del agente. Obteniendo primero las coordenadas (izquierda, derecha, arriba y abajo) de la posición donde se graficó al agente y luego usando numpy se extrae la sub-matriz del bounding box que se representa con un array numpy con las presiones actuales de CA. Sobre ese array numpy después se hacen los cálculos de las diferencias de presiones, usando las ecuaciones vistas en \eqref{eq:dP}.

De esta manera podemos rescatar la fuerza que siente el agente y que afectará al mismo mediante ecuaciones de movimiento. Ahora que los agentes son capaces de sensar el entorno dinámico en el que se encuentran y son afectados por el mismo, lo primero interesante que podemos pensar es que perderíamos el flocking logrado por nuestros agentes. Esto sucede, pero por un tiempo determinado y dependiendo de la intensidad del flujo de presión en el entorno y las masas de los agenetes. Una diferencia de presión determinada tendrá menos efecto en un agente a medida que el mismo aumente su masa, como es de esperar. 

Sin embargo, la forma en la que afecta la presión a un agente disminuye con el tiempo ya que el entorno dinámico nos asegura que la misma fluirá a lo largo del entorno. Otro punto que nos asegurará que el agente no vea afectado de forma definitiva su curso es el agregado de una fuerza de fricción al sistema. De esta manera cuando su velocidad se vea demasiado afectada por una gran diferencia de presión, el agente será impulsado en la dirección de la fuerza calculada, pero en su curso perderá velocidad gracias a la fricción. Dicha fricción se aplicará hasta alcanzar una velocidad mínima o característica que se desee de los agentes, de forma de prevenir una energía cinética nula en los mismos y dejarlos moverse libremente. 

Con estos datos tomados en cuenta, se puede lograr recuperar el flocking de los agentes. Situación más que interesante porque demuestra la robustéz del flocking, el cual tras haber sido desarmado por un estado particular de una propiedad del entorno, puede recuperarse. Esto creemos que brinda un comportamiento más natural a un video juego, pudiendo aumentar la inmersión en el mismo. Aunque también, debido al realizmo que se puede obtener, es factible de aplicar en simulaciones que intenten estudiar evoluciones de posibles situaciones reales y cómo estas pueden afectar a objetos o agentes de estudio. Simulaciones que busquen, por ejemplo, analizar el comportamiento de un grupo de personas al intentar auto-evacuarse de un entorno que se prende fuego en determinadas zonas. Permitiendo analizar dónde ubicar salidas de emergencia para dicho entorno.

Un ejemplo del acople aquí comentado lo podemos ver en la Figura \ref{acople-agentes}.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=7cm, width=0.95\textwidth]{img/Castro_Carbajal_Fig1.eps} 
}
\caption{Acople de agentes y entorno dinámico, con objetos fijos que impiden el flujo de presión.}
\label{acople-agentes}
\end{figure}


\newpage
\section{• Conclusiones} \label{section-conclusiones}
Lo que se hizo aquí fue estudiar algunas técnicas de swarm intelligence para ver cómo estas pueden ayudar al desarrollo de videojuegos, en principal a desarrollar controladores de agentes autónomos. Esto nos llevó a estudiar, parte por motivación, técnicas de inteligencia artificial que ayuden a desarrollar simulaciones de entornos dinámicos.

Luego de desarrollar un controlador para los agentes basado en un modelo continuo, en donde se eligió utilizar el potencial de Morse para dafinir la interacción entre los agentes, se llegó a la conclusión de que la customización de dicho algoritmo, para producir distintos comportamientos que pueden tener los agentes de un videojuego, es muy sensible. Con esto lo que se intenta decir es que si bien el controlador desarrollado simplemente con la interacción basada en Morse permite formar patrones interesantes (como la dona) y predecirlos, vimos que al acotar la función (introduciendo una visión en forma de cono) no se logró recuperar la formación deseada. Esto lo vemos como un impedimento a la hora de pensar un desarrollo de videojuegos o el papel que tendrá cada grupo de agentes en el mismo.

Sin embargo, esto no quita que esta técnica sea usada para algunos actores \textit{extras} del videojuego, actores no principales y que no se espere una participación especial de ellos. De esta manera podemos salvar un comportamiento no esperado y codificar un controlador de este grupo de actores usando el modelo continuo visto, pero sin que peligre la jugabilidad del videojuego. Por ejemplo, se puede usar para simular un cardúmen de peces o bien alguna manada de animales, siempre y cuando nuestro juego no se centre en interactuar con estos, al menos hasta un futuro, en donde podamos estudiar con más detalle este tipo de modelos ya sea con el potencial de Morse, variaciones del mismo u otros. Al momento de esta publicación no consideramos que el estudio e implementación hecho tenga la maduración suficiente para una aplicación directa en el desarrollo de videojuegos.

Por otro lado, al aplicar técnicas basadas en reglas (modelo discreto), vimos que éstas tienen un comportamiento muy bueno para la formación de flocking. No solo eso, sino que permiten que el desarrollador las use junto a otras características, como por ejemplo su acople con sensores. Esto hace que sea mucho más directo su aplicación en un videojuego, razón por la cual se eligió para la presentación del trabajo en WAVi 2010. 

También llegamos a la conclusión que las reglas permiten simular distintos tipos de comportamientos, para lo cual se debe hacer un estudio exhaustivo de lo que se desea simular y de esta forma poder discernir entre las reglas que se deben cumplir, cuales son las que rigen su comportamiento. Siempre teniendo en cuenta que hay que tratar de mantener el conjunto de reglas lo más reducido y genérico posible, tarea que no consideramos trivial. Debemos aclarar que una vez definida las reglas, el desarrollador tendrá que customizar de seguro muchas variables. Reglas como \textit{''alejarse del calor"} pueden parecer simples, pero no será trabajo simple encontrar una respuesta acorde a preguntas como: \textit{¿Cuánto alejarse?, ¿En qué sentido?, ¿Cuánto calor soportar antes de alejarse?, etc.}

Para encontrar respuestas a esas preguntas es que se propone usar conocimientos de otras áreas, en lo posible relacionado a lo que se desea simular. Por ejemplo, si se quiere simular una persona entonces estudiaremos qué temperatura es la que provoca incomodidad o peligro a una persona, y también debemos tener en cuenta el entorno en el que queremos que se desarrolle el videojuego. No serán los mismos valores que se darán a una grupo de agentes autónomos que simularán bomberos que a un grupo de agentes autónomos que simularan personas en un centro comercial.

Se cree que puede ser muy interesante tratar de dar respuestas a estas preguntas haciendo uso de conjuntos difusos. Esto creemos que puede ser buen complemento del trabajo aquí presentado ya que con el uso de conjuntos difusos las cuantificaciones se pueden simplificar y se esperaría un comportamiento suave de los agentes. Sobre todo, luego del estudio e implementación de sensores, creemos que ese puede ser un lugar más que propicio para estudiar y continuar el presente trabajo.

En lo que respecta a la simulación de entornos dinámicos, se llega a la concluciones que aplicar técnicas que son ampliamente utilizadas en la comunidad académica, como lo son los CA, representan una solución más que interesante. En este trabajo explicamos una forma de interpretar un entorno y simularlo con un CA. Se tuvo en cuenta la composición del entorno, cuestión que se implementaba de acuerdo a las reglas de actualización del CA, haciendo uso de la porosidad de las celdas, la pérdida de presión, o si la celda era inherte o no. Con esto vimos la creación de paredes, por ejemplo, que nos permite diseñar un entorno a medida, donde el flujo de la presión se vio afectado por la diferencia de materiales ya que las paredes no le permitían fluir.

Pero si bien las características de un CA para la simulación de entornos dinámicos nos da una gran libertad al momento para simular distintos medios con un comportamiento realista, vemos como punto negativo lo costoso de los cálculos. En el presente trabajo se decidió utilizar matrices para el CA, y actualizar el estado del autómata es muy costoso, ya que se debe recorrer y aplicar las reglas para cada celda. Si bien se usaron técnicas como una variable extra para guardar la presión futura y otra para el tiempo de actualización del CA, de modo que no se necesite recorrer la matriz dos veces (una para aplicar las reglas y otra para actualizarla), los cálculos hacen imposible mantener una cantidad de fps alta. 

Como aquí presentamos un esquema de acoplamiento de CA con agentes que se mueven a tiempo real, los algoritmos eficientes de actualización son estrictamente necesarios. Al tiempo de esta publicación nuestro CA se actualiza de manera no optimizada, especialmente notorio cuando el fenómeno natural que deseamos simular se propaga muy rápidamente, como las explosiones; en \cite{ca-modeling} se brindan soluciones usando octrees o quadtrees. Sin embargo nuestro aporte a la publicación de Tom Forsyth\cite{ca-modeling} radica en el acople con agentes y técnicas de flocking.

Variaciones al esquema pueden encontrarse en los trabajos de C.G. Bauza \cite{cgarcia-lattice} que han demostrado ser altamente eficientes. Existen otras técnicas empleadas para el simulado de explosiones en videojuegos, entre ellas los {\it sistemas de partículas} \footnote{Artículo online describiendo el algoritmo básico \url{http://www.gamasutra.com/view/feature/2122/building_a_millionparticle_system.php}}, que han alcanzado un alto nivel de desarrollo.

Con respecto a la performance se hicieron pruebas de ejecucion con y sin explosiones de 500 iteraciones cada una en su bucle de actualización principal. Se determinó que si ocurren muchas explosiones entonces el tiempo de ejecución puede subir a más del 350\%, siendo que el 75\% de este tiempo es consumido por las funciones que propagan las explosiones. Es por esto que hacemos la mención de la performance en la actualización del CA. 

La topología de grilla utilizada en nuestra aplicación no es necesaria. El automata celular puede implementarse sobre un grafo arbitrario. Esto brinda flexibilidad al modelado del escenario. Trabajos en esta dirección son llevados a cabo en academia, sin embargo la transferencia al mercado de los videojuegos es alarmantemente lenta.

Cabe señalar que en videojuegos, la precisión de las simulaciones de fenómenos físicos no es una necesidad, simplemente necesitamos captuar el comportamiento cualitativo del fenómeno. Este hecho pareciera indicar que una base en física o control (para los comportamientos de los agentes) no son requerimientos. Sin embargo, solo el concimiento adecuado de técnicas en dichas disciplinas permite desarrollar simplificaciones efectivas y útiles para videojuegos, y a la vez acelera la transferencia de desarrollos.




\newpage
\bibliography{referencias/referencias}

\end{document}
